【LeetCode日记】 1332. 删除回文子序列

LeetCode 上有很多抖机灵的题目，需要你仔细审题，否则很容易被套路。这里就有一道，我们来看下。

​

原题地址：https://leetcode-cn.com/problems/remove-palindromic-subsequences/

题目描述

s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。

返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

 

示例 1：

输入：s = "ababa"
输出：1
解释：字符串本身就是回文序列，只需要删除一次。
示例 2：

输入：s = "abb"
输出：2
解释："abb" -> "bb" -> "".
先删除回文子序列 "a"，然后再删除 "bb"。
示例 3：

输入：s = "baabb"
输出：2
解释："baabb" -> "b" -> "".
先删除回文子序列 "baab"，然后再删除 "b"。
示例 4：

输入：s = ""
输出：0
 

提示：

0 <= s.length <= 1000
s 仅包含字母 'a'  和 'b'
在真实的面试中遇到过这道题？

思路

这又是一道“抖机灵”的题目，类似的题目有1297.maximum-number-of-occurrences-of-a-substring

由于只有 a 和 b 两个字符。其实最多的消除次数就是 2。因为我们无论如何都可以先消除全部的 1 再消除全部的 2（先消除 2 也一样），这样只需要两次即可完成。 我们再看一下题目给的一次消除的情况，题目给的例子是“ababa”，我们发现其实它本身就是一个回文串，所以才可以一次全部消除。那么思路就有了：

• 如果 s 是回文，则我们需要一次消除
• 否则需要两次
• 一定要注意特殊情况， 对于空字符串，我们需要 0 次

代码

代码支持：Python3

Python3 Code:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == '':
            return 0
        def isPalindrome(s):
            l = 0
            r = len(s) - 1
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        return 1 if isPalindrome(s) else 2

如果你觉得判断回文不是本题重点，也可以简单实现：

Python3 Code:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == '':
            return 0
        return 1 if s == s[::-1] else 2

关键点解析

• 注意审题目，一定要利用题目条件“只含有 a 和 b 两个字符”否则容易做的很麻烦