LeetCode 刷题记录: 5. Longest Palindromic Substring [Python]

原题

https://leetcode.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

思路

马拉车方法 (Manacher’s Algorithm) 利用回文的性质减少运算。

  1. 考虑到回文中心可能位于两字符之间,将字符串之间的间隔使用符号(#)代替。

  2. 定义radius数组,记录每个位置的最大回文半径。

  3. 对于一个回文串的中心c,令R为这个回文串的右半径(R=c+radius[c]),即回文串范围为[c-R, c+R]。根据回文的性质,右半径内的字符 i(i->(c, c+R))其回文半径与回文串左半径内的镜像字符 j(j=(2*c-i))有关。当:

    • j的回文范围在回文串范围以内时,i的回文与j的回文完全一致。 (radius[i]=radius[j])

    • j的回文范围在回文串范围以外时,只能确保i的回文范围在右半径R之内。 (radius[i]>=R-i+1)

  4. 尝试扩展i的回文范围,考察T[i+radius[i]]==T[i-radius[i]]。若属于3.1情况将直接跳出。若属于3.2情况将扩大i的回文范围。

  5. 当i的回文范围大于右半径R时,将该位置作为中心(c=i),定义右半径R(R=c+radius[c]),重复步骤345。
    记录radius以及回文串的最大值。所有位置遍历完后返回最大回文串。

代码

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
class Solution:
"""
@param s: input string
@return: the longest palindromic substring
"""
def longestPalindrome(self, s):
# write your code here
if not s:
return s
T = '#'
for c in s:
T += c
T += '#'
radius = [0]*len(T)

c, r = 0, -1
maxr, maxs = -1, ''
for i in range(len(T)):
if r > i:
j = c-i-c
radius[i] = min(radius[j], c+r-1)

while -1 < i-radius[i] and i+radius[i] < len(T):
if T[i-radius[i]] == T[i+radius[i]]:
radius[i] += 1
else:
break

if radius[i] >= r:
c, r = i, radius[i]-1
if r > maxr:
maxr = r
maxs = s[(i-r)//2 : (i+r)//2]

return maxs

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×