Remove Palindromic Subsequences
给一个字符串,由a和b组成, 每一个step可以移除一个回文, 问需要多少step能移除这个string. 这个题很有意思, 需要观察一下ab能组成的可能string. 一个a和一个b就是step 1, 两个可以是aa,bb, ab 那么都是step 1, 三个可以是aaa, bbb, aba, aab, bba, bab, ….. 那么可以看出 两个字符组成的字符串要不是回文+单一字符, 要不是全是回文.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public int removePalindromeSub(String s) { if(s == null) return 0; int size = s.length(); if(size == 0) return 0; if(size == 1) return 1; int i = 0; int j = size - 1; while(i <= j) { if(s.charAt(i) != s.charAt(j)) return 2; i++; j--; } return 1; } } |