題目在此 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:
mirror = 2 * rightmost_center_index - center_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
|
也許你也會想看看