LeetCode 筆記 - 647. Palindromic Substrings

題目在此 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 字串就是迴文,而我們可以找出幾種可能 abccbabccb 還有 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

也許你也會想看看