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, ….. 那么可以看出 两个字符组成的字符串要不是回文+单一字符, 要不是全是回文.
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;
}
}