[LeetCode] 1332. 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".

Constraints:

• 1 <= s.length <= 1000
• s[i] is either 'a' or 'b'.

这道题给了一个只有字母a和b的字符串，说是每次可以删除一个回文子序列，问最少需要删除多少次，可以将给定字符串变为空串。一般来说对于 Easy 题目来说，基本都是看完题直接无脑写代码的，但是这道题刚开始博主没有看清题意，以为是删除回文子串，心想这有点难啊，怎么可能是道简单题。后来一看原来是回文子序列，瞬间难度就降了不少。虽然难度降低了，但实际上还有一个点，如果没想到也不容易解题，那就是每次移除所有相同的字母，因为相同的字母话，不管多少个，一定是回文串。

又因为题目中说了只有a和b两个字母，那么最多只需要2次就可以清空字符串。再想想什么情况下可以小于2，当给定字符串是空串的话，不用移除，当然题目中限定了字符串长度至少为1。再有就是假如给定的字符串本身就是回文串的话，那么直接一次就能可以全部移除了，所以这道题的返回值只有两种，1或2。想通了这些，代码就很好写了，只需要判断一下给定的字符串是否是回文串就行了，这里用双指针来一个一个的比较对应字母就行了。首先判空，若为空直接返回0（虽然题目限定了不为空，出于职业习惯，还是加上了）。然后调用子函数判断是否为回文串，是的话返回1，否则返回2，参见代码如下：

解法一：

class Solution {
public:
    int removePalindromeSub(string s) {
        if (s.empty()) return 0;
        return isPalindrome(s) ? 1 : 2;
    }
    bool isPalindrome(string s) {
        int left = 0, right = (int)s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            ++left; --right;
        }
        return true;
    }
};

还有一种检测回文串的方法，就是将字符串翻转一下，若和原字符串相同，则是回文串，这也是回文串的定义。这里可以一行解题，用2减去判断是否是回文串的结果，是回文串的话就会减去1，然后再减去判断空串的结果，若是空串就会减去1，总之一行搞定碉堡了，参见代码如下：

解法二：

class Solution {
public:
    int removePalindromeSub(string s) {
        return 2 - (string(s.rbegin(), s.rend()) == s) - s.empty();
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1332

参考资料：

https://leetcode.com/problems/remove-palindromic-subsequences/

https://leetcode.com/problems/remove-palindromic-subsequences/solutions/490303/java-c-python-maximum-2-operations/

LeetCode All in One 题目讲解汇总(持续更新中...)