題目地址（1332. 刪除回文子序列）
https://leetcode-cn.com/problems/remove-palindromic-subsequences/
題目描述
返回刪除給定字符串中所有字符（字符串為空）的最小刪除次數(shù)羽嫡。
「子序列」定義：如果一個(gè)字符串可以通過刪除原字符串某些字符而不改變?cè)址樞虻玫街景颍敲催@個(gè)字符串就是原字符串的一個(gè)子序列。
「回文」定義：如果一個(gè)字符串向后和向前讀是一致的宪摧，那么這個(gè)字符串就是一個(gè)回文球及。
示例 1：
輸入：s = "ababa"
輸出：1
解釋：字符串本身就是回文序列氧骤，只需要?jiǎng)h除一次。
示例 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'
在真實(shí)的面試中遇到過這道題？
思路
這又是一道“抖機(jī)靈”的題目姑蓝，類似的題目有1297.maximum-number-of-occurrences-of-a-substring
由于只有 a 和 b 兩個(gè)字符鹅心。其實(shí)最多的消除次數(shù)就是 2。因?yàn)槲覀儫o論如何都可以先消除全部的 1 再消除全部的 2（先消除 2 也一樣）纺荧，這樣只需要兩次即可完成旭愧。 我們?cè)倏匆幌骂}目給的一次消除的情況，題目給的例子是“ababa”宙暇，我們發(fā)現(xiàn)其實(shí)它本身就是一個(gè)回文串输枯，所以才可以一次全部消除。那么思路就有了：
- 如果 s 是回文占贫，則我們需要一次消除
- 否則需要兩次
- 一定要注意特殊情況桃熄， 對(duì)于空字符串，我們需要 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
如果你覺得判斷回文不是本題重點(diǎn)型奥，也可以簡(jiǎn)單實(shí)現(xiàn)：
Python3 Code:
class Solution:
def removePalindromeSub(self, s: str) -> int:
if s == '':
return 0
return 1 if s == s[::-1] else 2
關(guān)鍵點(diǎn)解析
- 注意審題目瞳收，一定要利用題目條件“只含有 a 和 b 兩個(gè)字符”否則容易做的很麻煩
