Longest Palindromic Substring

LeetCode 5. Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S.
给定一个字符串 S,找到其中最长的连续回文串。

暴力法

最先想到的是暴力法,找到所有可能的字符串然后判断是否是回文。可能的字符串一共有 $n(n-1)/2$,判断一个字符串是否为回文所需时间为 $O(n)$,则时间复杂度为 $O(n^3)$,效率太低。

从中心往外延伸

我们可以利用回文的特点来提高算法的效率。从单个字符或一对字符开始,然后慢慢向两边扩展,若两边添加的为相同字符则继续,否则开始下一轮。这样我们就可以把所需判断的字符串个数,从 $n(n-1)/2$ 减少为 $2n -1$,时间复杂度降为 $O(n^2)$。
具体 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
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
start = 0
end = 0
for index in range(len(s)):
len1 = self.expandString(s, index, index)
len2 = self.expandString(s, index, index + 1)
result = max(len1, len2)
if result > (end - start + 1):
end = index + result // 2
start = end - result + 1
return s[start:end + 1]
def expandString(self, s, left, right):
begin = left
end = right
while begin >= 0 and end < len(s) and s[begin] == s[end]:
begin -= 1
end += 1
return end - begin - 1

Manacher’s Algorithm

是否还有继续提升的空间呢?答案是肯定的。有一种神奇的算法 Manacher’s Algorithm,时间复杂度竟然只有 $O(n)$。

1
2
# c # a # b # a # a # b # a # a #
0 1 0 1 0 3 0 1 6 1 0 ?

举个例子来简单说明这个算法是怎么工作的。
上面一行是字符串,其中 # 是插入到字符之间的特殊符号,使我们可以统一处理奇数长和偶数长的回文。
下面一行代表以当前位置为中心,最长回文的长度。

1
2
3
[ i'c i ]
# c # a # b # a # a # b # a # a #
0 1 0 1 0 3 0 1 6 1 0 ?

假设我们现在已经知道 $c$ 及之前位置最长回文的长度,那么 $i$ 位置上的数字应该是多少?
由于回文的对称性,$i$ 位置上的数字应该与 $i’$ 位置上的相同,即 1。

1
2
3
[ j' c j ]
# c # a # b # a # a # b # a # a #
0 1 0 1 0 3 0 1 6 1 0 ?

那么 $j$ 的数字呢,是否也和 $j’$ 一样?
不巧的是,以 $c$ 为中心的回文只能保证在 [ ] 之间的对称性,对超出其范围的无能为力。
由于 $j$ 和 ] 相差 3,$j’$ 的数字为 3,因此 $j$ 的数字必定大于等于 3。之后再往两边延伸,发现最终为 5。

关于算法更详细的说明可以看这里
下面是 Manacher’s Algorithm 的 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
class Solution(object):
def longestPalindrome2(self, s):
newS = '^#%s#$' % '#'.join(s)
length = len(newS)
pArr = [0] * length
center, right, i = 0, 0, 0
for i in range(length - 1):
i_mirror = 2 * center - i
if right > i:
pArr[i] = min(right - i, pArr[i_mirror])
else:
pArr[i] = 0
while newS[i + 1 + pArr[i]] == newS[i - 1 - pArr[i]]:
pArr[i] += 1
if i + pArr[i] > right:
center = i
right = i + pArr[i]
maxLen, centerIndex = 0, 0
for j in range(length):
if pArr[j] > maxLen:
maxLen = pArr[j]
centerIndex = j
start = (centerIndex - maxLen - 1) // 2
return s[start:start + maxLen]

参考