5. 最长回文子串

发表于 更新于 分类于

1. 简介

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

2. 题解

2.1. 动态规划

如果字符串 s 是回文串，并且长度大于等于 3，那么字符串 s 去除首尾两个字符的子串也是回文串

长度为 1 的字符串一定是回文串

以 "ababa" 为例1，如果已知 "bab" 是字符串是回文串，因为 "ababa" 首尾是相同字符 "a"，那么 "ababa" 也是回文串。

设 $P(i, j)$ 表示 s 的子串 s[i, j] 是否为回文串，即

s[i, j] 表示 s 的第 i 到第 j 个字符组成的字符串，可取到右边界

其他情况包括以下两种可能性：

  1. s[i, j] 不是回文串；
  2. i>j 。

根据上述的公式，可得动态规划的状态转移方程：

即：子串为回文串 且 当前字符串的首尾字符相同

初始状态：

  1. 字符串长度为 1，一定是回文串，即 $P(i,i)=True$；
  2. 字符串长度为 2，如果字符相同则为回文串，即 $P(i,i+1)=(s[i]==s[j])$ 。

我们用图片来展示动态规划的流程：

图1 字符串s和动态规划矩阵dp

图2 初始化dp

初始化 dp，首先 dp[i][i]=True，表示字符串长度为 1 的一定是回文子串，如果 s[i]==s[i+1]，则 dp[i][i+1]=True，否则 dp[i][i+1]=False。在初始化的过程中，记录最长回文子串的起始位置和对应的长度。

图3 遍历长度为3的子串

初始化时把长度为 1 和长度为 2 的子串遍历完了，下面直接从长度为 3 的子串开始遍历。

首先是 s[0, 2]，因为 s[1, 1]^(s[i]==s[j]) = True，此时更新最长回文子串的起始位置为 0，长度为 3。

图4 继续遍历长度为3的子串

遍历下一个长度为 3 的子串中，此时的子串为 s[1, 3]，有 s[2, 2]^(s[1]==s[3]) = True，这个回文子串没有大于 3，可以不用更新最长回文子串。

图5 全部子串遍历完成

全部子串（包括长度大于3的子串）遍历完成后得到的上图结果，返回最长回文子串即可。

根据上述过程，实现的 python 代码如下

  • 时间复杂度：$O(N^2)$
  • 空间复杂度：$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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n<=1:                  # 长度为1，一定是回文串
            return s
        dp = [ [False]*n for _ in range(n)]
        max_len = 1               # 最长回文子串长度
        start = 0                 # 最长回文子串长度起始位置
        for i in range(n):        # 初始化
            dp[i][i] = True
            if i<n-1 and (s[i]==s[i+1]):
                dp[i][i+1] = True
                max_len = 2
                start = i
        for L in range(3, n+1):   # 子串长度
            for i in range(n):    # 起始位置
                j = L + i - 1     # 终止位置，取决于子串长度和起始位置
                if j>=n:          # 终止位置索引越界
                    break
                dp[i][j] = dp[i+1][j-1] and (s[i]==s[j])
                if dp[i][j] and (j-i+1)>max_len:
                    max_len = j - i + 1
                    start = i
        return s[start: start+max_len]

2.2. 中心扩展

观察状态转移方程

找出其中的状态转移链

可以发现，所有状态在转移的时候可能性都是唯一的1，如果我们从每一种边界情况开始扩展，就可以得到所有状态对应的答案。

图6 边界子串长度为1

边界子串长度为 1 的情况

图7 边界子串长度为2

子串长度为 2 的边界情况

边界即子串长度为 1 或 2，如果两边的字母相同，我们就可以继续扩展，从 $P(i+1,j-1)$ 扩展到 $P(i,j)$，如果两边的字母不同，说明这之后的子串都不是回文串，停止扩展。实现的 python 代码如下

  • 时间复杂度：$O(N^2)$
  • 空间复杂度：$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        start, end = 0, 0
        for i in range(n):
            left1, right1 = self.expand_around_center(s, i, i)   # 从1个字符开始扩展
            left2, right2 = self.expand_around_center(s, i, i+1) # 从2个字符开始扩展
            if right1-left1 > end-start:
                start, end = left1, right1
            if right2-left2 > end-start:
                start, end = left2, right2
        return s[start: end+1]
            
    def expand_around_center(self, s, i, j):
        n = len(s)
        while i>=0 and j<n and s[i]==s[j]:
            i -= 1
            j += 1
        # 结束循环时，有 i<0且j>n，或者 s[i]!=s[j]
        # 所以我们 i+1，j-1，回退到最后一个符合条件的位置
        return i+1, j-1

2.3. Manacher算法

Manacher 算法（马拉车算法）本质上还是用中心扩展的思想2，回文串可分为奇数回文串和偶数回文串，它们的区别是：奇数回文串关于它的“中点”满足“中心对称”，偶数回文串关于它“中间的两个点”满足“中心对称”。

为了消除字符串长度是奇数和偶数带来的差异，首先需要对字符串进行预处理，也就是添加分隔符：在字符串的首尾、相邻的字符中插入分隔符，例如 "baba" 添加分隔符 # 以后得到 "#b#a#b#a#" 。

插入分隔符后，不管原字符串长度是奇数还是偶数，最后得到的都是奇数长度的字符串。

图8 原字符串插入分隔符

我们计算每个位置 i 开始向外扩展的最大回文子串长度，在此过程中记录最大的回文子串长度即可。在计算以 i+1 为中心的回文子串长度时，我们可以利用位置 i 上的信息。分 2 种情况讨论：

r 表示当前位置 i 向外扩展的最大右边界，数组 P 来记录每个位置向右扩展的最大长度。

c 表示目前找到的最长回文子串的中心位置，并用 max_len 记录最大回文子串长度。

图9 从位置i开始向外对扩展

假设我们目前找到的最长子串中心位置为 c=6 ，该位置的最大扩展右边界为 r=10，对于以 c 为中心的任何一个回文字符串来说，r 关于 c 的镜像的索引是 l = 2*c - r 。Manacher 的核心就是借助 c、r、l 提供的信息，在求 P[i] 的时候，不用暴力地向两侧扩展，易知以位置 i 为中心的回文字符串的长度为 2*P[i]+1。

（一）第一种情况，镜像索引向左扩展的步长没有超过已知最大回文子串的左边界，那么 i 处至少可以向外扩展 P[i'] 步

图10 第一种情况

如图所示，此时 i < r，我们不用直接从 i=7 处向外扩展，可以先计算以 i=7 为中心的最短回文串长度，在此基础上得到 P[i]。

先计算 i 的关于 c 的镜像索引 i' = 2*c -i，如果 i' - P[i'] 没有小于 l ，即从位置 i' 向外扩展 p[i'] 步后，没有超出已知最大回文子串的左边界，那么位置 i 至少可以向外扩展 P[i'] 步。

这里利用的是以 c 为中心的回文字符串的对称性，只要没有超过这个回文字符串的边界，从 i 往右、左走多少步，和从 i' 往左、右走多少步所看到的字符时一样的，所以在此条件下 i' 能往左走多少步，i 就能往右走多少步。

位置 i 实际可以向外扩展的长度可能会更大，所以还需要在此基础上继续扩展。

（二）第二种情况，即 i' - P[i'] 小于 l，那么 i 处至少可以向外扩展 r-i 步

图11 第二种情况

如图所示，此时 i'-P[i']=0 ，而 l=2 ，即从位置 i' 向外扩展 P[i'] 步后，超出已知最大回文子串的左边界，所以 P[9] 至少为 r - i = 3 。

即以 i 为中心的最小回文字符串，向右扩展的长度不超过已知最大回文子串的右边界 r，图中例子 r 刚好在边界处。

如果 r 不是边界，假设上述字符串 s 长度不止 13，且以 i=9 为中心的回文字符串，有 s[13]=s[5]='a'，此时会有 s[1]=s[13]='a'，那么以 i=7 为中心的最长回文子串长度就变长了，不止是 5；如果 s[13]≠'a'，在此情况下刚好向右扩展 r-i=12-9=3 步。

上面两种情况满足公式：

然后从 i 左右 P[i] 的位置处继续向两侧扩展即可，如果以 i 为中心的回文字符串的右边界超过了 r，则更新 c 为i ，更新 r 为 i + P[i]。实现的 python 代码如下3：

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$
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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = "#" + "#".join(s) + "#"
        N = len(s)
        P = [0] * N
        c, r = 0, 0
        max_len = 0        # 最大回文子串长度
        start, end = 0, 0  # 最大回文子串的起始和结束位置
        for i in range(N):
            i_mirror = (2 * c) - i
            
            if i < r:
                P[i] = min(r - i, P[i_mirror])
            # 开始中心扩展
            a = i - (1 + P[i])
            b = i + (1 + P[i])
            P[i] = self.expand_length(s, a, b)
            
            # 查看当前位置 i 中心扩展后，当前右边界是否超过之前的最大右边界
            # 如果是，则更新最大回文子串的 c 和 r
            if i + P[i] > r:
                c = i
                r = i + P[i]
                # 判断是否为更长的回文子串
                if (2*P[i]+1) > max_len:
                    max_len = 2 * P[i] + 1
                    start = 2 * c - r 
                    end = r
        res = s[start: end+1]
        res = '' .join(res.split('#'))
        return res
    
    def expand_length(self, s, i, j):
        n = len(s)
        while i>=0 and j<n and s[i]==s[j]:
            i -= 1
            j += 1
        # 最大回文子串长度 L = (j-1) - (i+1) + 1 = j - i - 1
        # 则需要向左向右扩展 P[i] = (L-1)//2
        L = j - i - 1
        return (L-1)//2

参考资料

1. https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/ ↩