leetcode-1332-easy

Remove Palindromic Subsequences

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.
Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".
Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

思路一：题目意思理解错了，subsequences 意思是可以不用连续的，结果这题卡了很久。理解正确意思后就好处理了，只有两个字符，删掉其中一个字符就满足提交了。所以判断一下字符串是否是回文，不是回文才需要删除操作，最多需要两次

public int removePalindromeSub(String s) {
char[] chars = s.toCharArray();
return isPalindromic(chars) ? 1 : 2;
}

public boolean isPalindromic(char[] chars) {
    int begin = 0;
    int end = chars.length - 1;
    while (begin < end) {
        if (chars[begin++] != chars[end--]) return false;
    }
    return true;
}

原文地址：http://www.cnblogs.com/iyiluo/p/16833200.html