LeetCode 筆記 - 1332. Remove Palindromic Subsequences

Posted on

題目在此 1332. Remove Palindromic Subsequences

給定一個僅包含 a, b 的字串，一次可以移除一個迴文字串，請計算出將字串清空的移除次數

解題思維

同學，不要看到迴文就直接先上 Manacher’s Algorithm，先仔細想想
如果有興趣可以參考這篇 LeetCode 筆記 - 5. Longest Palindromic Substring

這裡有個地方需要注意的是，當移除迴文字串的時候，所有相符字串都會被一起移除
理解到這裡其實就很簡單了

因為題目字串只包含 a, b，所以當移除了 a 時，剩下的 b 就會自動變成迴文字串了
也就是說當原本字串就是迴文字串時，清空次數就是 1，不然就只會是 2

程式碼

1
2
3
4
5
class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == s[::-1]:
            return 1
        return 2

完成♥️

也許你也會想看看