LeetCode 筆記 - 647. Palindromic Substrings

Posted on

題目在此 647. Palindromic Substrings

給定一個字串，請給出所有迴文的數量

解題思維

這題又是 Manacher’s Algorithm 的主戰場
這演算法可以利用迴文的特性，將複雜度降到 O(n)

有關這個演算法的詳細說明與推導可以參考之前的筆記
LeetCode 筆記 - 5. Longest Palindromic Substring

因為這個演算法算出的迴文半徑，是原始字串的兩倍
所以最後的答案是半徑除以 2

舉例子

abccba 使用 Manacher’s Algorithm 算出來的結果為
0, 0, 1, 0, 1, 0, 1, 6, 1, 0, 1, 0, 1, 0, 0

其中 6 代表整個 abccba 字串就是迴文，而我們可以找出幾種可能 abccba、bccb 還有 cc
我們可以看到有 3 種，而剩下的 1 就是只有自己本身，那也加起來

總共就是 9 種

完成 ♥️

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution:
    def countSubstrings(self, s: str) -> int:
        
        if (length := len(s)) <= 1:
            return 1
        
        padding_s = f"^_{'_'.join(s)}_$"
        padding_length = len(padding_s)
        
        PLS_radius = [0] * padding_length
        
        rightmost_right_index = 0
        rightmost_center_index = 0
        
        for center_index in range(padding_length):
            LPS_result = 0
            
            if center_index < rightmost_right_index:
                # center_index - (center_index - rightmost_center_index) * 2
                # center_index - center_index * 2 + rightmost_center_index * 2
                # rightmost_center_index * 2 - center_index

                mirror = 2 * rightmost_center_index - center_index

                # at first, remember
                # rightmost_right_index - center_index = mirror - rightmost_left_index

                # case 0: PLS_radius[mirror] < rightmost_right_index - center_index
                # 表示以 mirror 為中心的迴文字串沒有超過，目前最靠右邊的迴文字串範圍
                # 因為會以 rightmost_center_index 對稱，所以 PLS_radius[center_index] 會等於 PLS_radius[mirror]

                # case 1: PLS_radius[mirror] == rightmost_right_index - center_index
                # 表示以 mirror 為中心的迴文字串剛好等於目前最靠右邊的迴文字串範圍
                # 那就以 rightmost_right_index 開始掃描就可以了
                # PS: center_index + rightmost_right_index - center_index = rightmost_right_index

                # case 2: PLS_radius[mirror] > rightmost_right_index - center_index
                # 表示以 mirror 為中心的迴文字串超過，目前最靠右邊的迴文字串範圍
                # 因為超過 rightmost_right_index 的地方是未知
                # 所以從 rightmost_right_index 開始掃描
                # PS: center_index + rightmost_right_index - center_index = rightmost_right_index

                LPS_result = min(rightmost_right_index - center_index, PLS_radius[mirror])
            
            # 中心擴展算法
            for i in range(LPS_result, padding_length):
                if center_index - i < 0 or center_index + i >= padding_length:
                    break
                if padding_s[center_index - i] != padding_s[center_index + i]:
                    break
                LPS_result = i
            PLS_radius[center_index] = LPS_result

            if center_index + LPS_result > rightmost_right_index:
                # 更新最右迴文字串右邊界
                rightmost_right_index = center_index + LPS_result
                # 更新最右迴文字串中心點
                rightmost_center_index = center_index
        
        result = 0
        for radius in PLS_radius:
            result += (radius + 1) // 2
            
        return result

相關文章