LeetCode 筆記 - 1332. Remove Palindromic Subsequences

題目在此 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

完成♥️

相關文章