LeetCode 5. 最长回文子串（中）

马拉车算法（Manacher's Algorithm）

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
1
2
输入: "cbbd"
输出: "bb"

考察知识点

字符串、数组、马拉车算法（Manacher's Algorithm）、中心对称约束

核心思想

参考链接1

1、先对字符串进行预处理，两个字符之间加上特殊符号# 2、然后遍历整个字符串，用一个数组来记录以该字符为中心的回文长度，为了方便计算右边界，我在数组中记录长度的一半（向下取整） 3、每一次遍历的时候，如果该字符在已知回文串最右边界的覆盖下，那么就计算其相对最右边界回文串中心对称的位置，得出已知回文串的长度 4、判断该长度和右边界，如果达到了右边界，那么需要进行中心扩展探索。当然，如果第3步该字符没有在最右边界的“羽翼”下，则直接进行中心扩展探索。进行中心扩展探索的时候，同时又更新右边界 5、最后得到最长回文之后，去掉其中的特殊符号即可

重点参考连接

有一种情况没有说明，比如i > mx的情况（例如刚开始对字符串进行遍历时），这种情况也是直接用中心展开求得半径

首先要利用中心展开算法求以某个特定节点为中心的最长回文。

1
2
3
4
5
6
7
8
def getExpandLength(left, right, s):
    '''
    中心展开求回文字符串长度
    '''
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

Python版本

一个不成功的版本

时间复杂度为 $ O(n^{2}) $，一但输入数据太长，就无法执行。

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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == "":
            return ""
        
        if len(s) == 1:
            return s

        left = 0 
        start_c = s[left]
        max_palindromes = ""
        max_palindromes_length = 0
        sing_palindrome = True

        while left < len(s):
            for i in range(left+1, len(s)):
                if s[i] == start_c:
                    is_palindrome = True
                    sub_str = s[left:i+1]
                    sub_str_len = len(sub_str)
                    # 检车是否为回文字符
                    if len(sub_str)%2==0:  # 偶数
                        mid = int(sub_str_len/2)
                        front = sub_str[:mid]
                        back = sub_str[mid:]
                    else: # 奇数
                        mid = int(sub_str_len/2)
                        front = sub_str[:mid]
                        back = sub_str[mid+1:]
                    mid_length = len(back)
                    # for j in range(len(back)-1, 0, -1):
                    for j,v in enumerate(front):
                        if v != back[mid_length-1-j]:
                            is_palindrome = False
                    if is_palindrome:
                        sing_palindrome = False
                        if sub_str_len > max_palindromes_length:
                            max_palindromes_length = sub_str_len
                            max_palindromes = sub_str
            left += 1
            if left < len(s):
                start_c = s[left]

        if sing_palindrome:
            return s[0]
        else:
            return max_palindromes

一个成功的Python版本

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
class Solution:
    def getExpandLength(self, left, right, s):
        '''
        中心展开求回文字符串长度
        '''
        # 假设输入的是left=4 right=6 s='babcbabcba' => 以i=5为中心向两边搜寻
        # 0 1 2 3 4 5 6 7 8 9
        # b a b c b a b c b a
        # 则 left = 3/2/1 和 right = 7/8/9 可构成回文 a b c b a b c b a
        # 此时当left再减少时 left=0 满足条件 right=10=len(s) 就不满足条件了 while循环结束 然后返回回文直径为 rigth - left - 1(i=5的中心点不计算在内) = 10-0-1 = 9 则半径为9//2=4向下取整
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1


    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2: return s
        s = '#' + '#'.join(list(s)) + '#'
        p = [0 for x in range(len(s))]
        max_id = -1
        max_radius = -1
        c = -1
        mx = -1
        for i in range(len(s)):
            if i > mx:
                radius = self.getExpandLength(i, i, s) // 2
                p[i] = radius
                c = i
                mx = i + radius  # mx = c + p[c] / min = c - p[c]
                if radius > max_radius:
                    max_id, max_radius = i, radius
            else:
                j = 2*c - i
                if j - p[j] > 2 * c - mx:  # 在C的radius范围内
                    p[i] = p[j]
                elif j - p[j] < 2 * c - mx:  # 越界了
                    p[i] = mx - i
                else:  # 如果不是上述两种情况 就说明j-p[j]==min，依赖之前的有效信息，以及无法为当前以i为回文中心，寻找最长回文字符半径提供依据，所以要调用getExpandLength方法，用中心拓展的方法手动扩展回文半径
                    radius = self.getExpandLength(i-p[j]-1, i+p[j]+1, s) // 2
                    p[i] = radius
                    if i + radius > mx:  # 如果以当前i所在位置为回文中心，其右边大于原来以c所在位置为回文中心的右边，则更新其回文中心为c，mx修正为新的右边 mx = i + radius
                        c = i
                        mx = i + radius
                    if radius > max_radius:  # 如果新的回文半径大于原max_radius 就更新新的radius
                        max_id, max_radius = i, radius
        return s[max_id-max_radius:max_id+max_radius+1].replace('#', '')


print("leet code accept!!!")
s = ["babad", "cabadabae", "ab", "aa", "abc", "cbbd", "babad"]
Answer = ["bab", "abadaba", "a", "aa", "a", "bb", "bab"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(s)):
        print("-"*50)
        result = solution.longestPalindrome(s[i])
        # print(result)
        # print(Answer[i])
        print(result==Answer[i])

一个更加高效的版本

推荐这个版本 优雅且兼具易读性 在理解了上面那个Manacher's Algorithm算法的基础上，理解这个会更加容易。

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
class Solution:
    def longestPalindrome(self, s) -> str:
        if len(s) < 2:
            return s
        # 先插入"#" 开头和结尾都要插入
        s = '#' + '#'.join(list(s)) + '#'
        # 申明radius list
        p = [0 for x in range(len(s))]
        # 申明剩余变量
        max_str = ""
        c = 0
        mx = 0
        for i in range(len(s)):
            if i < mx:  # i是在以某一z值为中心的最长回文子串的半径之内
                j = c * 2 - i  # j为i以c为原点的对称点 / i关于center的对称点
                p[i] = min(p[j], mx-i)  # 这行代码类似上面那个版本的下述
                """
                if j - p[j] > 2 * c - mx:
                    p[i] = p[j]
                elif j - p[j] < 2 * c - mx:
                    p[i] = mx - i
                """
            # 尝试继续向两边扩展，更新p[i]，如果不行就停止，问题也不大 注意添加判断条件 根据Python的判断条件 不满足下标条件的就不进行判等 所以判等条件放到最后
            while (i-p[i]-1) >= 0 and (i+p[i]+1) < len(s) and s[i-p[i]-1] == s[i+p[i]+1]:
                p[i] += 1
                if p[i] + i > mx:  # 向右边推动 更新中心
                    c = i
                    mx = p[i] + i
                if 1 + 2*p[i] > len(max_str):  # 更新最长串
                    max_str = s[i-p[i]:i+p[i]+1]
        return max_str.replace("#", "")

有效语法糖

1、声明长度为N的、每个元素都是0的数组

1
_list = [0 for x in range(len(s))]

2、在字符串的中间添加“#”

1
2
3
4
5
def preprocess(self, s: str) -> str:
    s_copy = "#"
    for i in s:
    s_copy = s_copy + i + "#"
    return s_copy

或者 Python join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串。

1
2
3
4
5
6
7
8
s = '#' + '#'.join(list(s)) + '#'
s1 = "-"
s2 = ""
seq = ("r", "u", "n", "o", "o", "b") # 字符串序列
print (s1.join( seq ))
print (s2.join( seq )
r-u-n-o-o-b
runoob

3、Python3的向下取整

1
2
>>> 13//2
6

4、此题目中，可能出现变量为0的情况，因此在初始化时，将各个变量初始化为了-1。需注意。

1
2
3
4
max_id = -1
max_radius = -1
c = -1
mx = -1

5、python3字符串替换

1
'a#b#c'.replace('#', '')