LeetCode 筆記 - 1930. Unique Length-3 Palindromic Subsequences

Posted on

題目在此 1930. Unique Length-3 Palindromic Subsequences

給定一個字串，請問裡面有幾個長度為 3 的迴文子序列？

解題思維

名詞解說：

這題很弔詭，看到 Subsequences 就會想到 DP，看到迴文就會想到 Manacher’s Algorithm，但是這題其實不用這麼複雜。

先分析一下題目，長度為 3 的迴文子序列，也就是說只要前後相同，中間就可以是任意字元。
題目也說了，相同組合的算一個，所以我們只要找到每個字元的第一個出現位置與最後一個出現位置，就可以知道這個字元可以組成幾個迴文子序列。image 106

所以這題的關鍵找到每個字元的第一個出現位置與最後一個出現位置就可以了，中間就用 set 來處理重複的字元。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:

        if (size := len(s)) == 3:
            return 1 if s[0] == s[-1] else 0

        s_set = set(s)

        result = 0
        for c in s_set:
            between_set = set(s[s.find(c) + 1:s.rfind(c)])
            result += len(between_set)

        return result
image 106

也許你也會想看看