# 1332. 刪除回文子序列 # 題目地址（1332. 刪除回文子序列） <https://leetcode-cn.com/problems/remove-palindromic-subsequences/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個字符串 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](https://github.com/azl397985856/leetcode/blob/77db8fa47c7ee0a14b320f7c2d22f7c61ae53c35/problems/1297.maximum-number-of-occurrences-of-a-substring.md) 由于只有 a 和 b 兩個字符。其實最多的消除次數就是 2。因為我們無論如何都可以先消除全部的 1 再消除全部的 2（先消除 2 也一樣），這樣只需要兩次即可完成。 我們再看一下題目給的一次消除的情況，題目給的例子是“ababa”，我們發現其實它本身就是一個回文串，所以才可以一次全部消除。那么思路就有了： - 如果 s 是回文，則我們需要一次消除 - 否則需要兩次 - 一定要注意特殊情況， 對于空字符串，我們需要 0 次 ## 關鍵點解析 - 注意審題目，一定要利用題目條件“只含有 a 和 b 兩個字符”否則容易做的很麻煩 ## 代碼 代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removePalindromeSub</span><span class="hljs-params">(self, s: str)</span> -> int:</span> <span class="hljs-keyword">if</span> s == <span class="hljs-string">''</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isPalindrome</span><span class="hljs-params">(s)</span>:</span> l = <span class="hljs-params">0</span> r = len(s) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> l < r: <span class="hljs-keyword">if</span> s[l] != s[r]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> l += <span class="hljs-params">1</span> r -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> isPalindrome(s) <span class="hljs-keyword">else</span> <span class="hljs-params">2</span> ``` ``` 如果你覺得判斷回文不是本題重點，也可以簡單實現： Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removePalindromeSub</span><span class="hljs-params">(self, s: str)</span> -> int:</span> <span class="hljs-keyword">if</span> s == <span class="hljs-string">''</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> s == s[::<span class="hljs-params">-1</span>] <span class="hljs-keyword">else</span> <span class="hljs-params">2</span> ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。