目录

0005:最长回文子串(★)

力扣第 5 题

题目

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

示例 1:

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

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

相似问题:

分析

#1

  • 暴力法是直接遍历所有子串,判断是否是回文
  • 显然有很多不必要的判断,观察发现回文子串是可以递推的
    • s[i:j+1] 是回文等价于 s[i-1:j] 是回文且 s[i]==s[j]。
  • 因此采用区间 dp
    • 令 dp[i][j] 代表 s[i:j+1] 是否回文,递推式为: $$dp[i][j] = dp[i+1][j-1] \ and \ s[i]==s[j]$$
    • dp[i][j] 依赖 dp[i+1][j-1],要特别注意遍历顺序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def longestPalindrome(self, s: str) -> str:
        l,r,n = 0,0,len(s)
        dp = [[1]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                dp[i][j] = dp[i+1][j-1] and s[i]==s[j]
                if dp[i][j] and j-i>r-l:
                    l,r = i,j
        return s[l:r+1]

时间 $O(N^2)$,1908 ms

#2

  • 注意到递推过程中假如 dp[i+1][j-1] 非真,就没必要递推 dp[i][j] 了
  • 因此考虑从初始的 dp[i][i-1] 或 dp[i][i] 往两边递推,一旦非真就停下来
  • 这就是中心扩展法:
    • 遍历所有中心 (i, i-1) 或 (i, i)
    • 对于每个中心,往两边扩展找到最长的回文子串
    • 过程中找到的最长的即为所求
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(l,r):
            while l and r<n-1 and s[l-1]==s[r+1]:
                l -= 1
                r += 1
            return l,r

        a,b,n = 0,0,len(s)
        for i in range(n):
            for l,r in [expand(i,i), expand(i,i-1)]:
                if r-l>b-a:
                    a,b = l,r
        return s[a:b+1]

时间 $O(N^2)$,301 ms

#3

  • 此题还有一个经典的的 Manacher算法
  • 它在 O(N) 时间内能找到
    • 每个中心子串的最长扩展距离
    • 每个下标结尾的最长回文子串
  • 因此在与回文相关的问题中,都可以尝试用 Manacher 算法解决。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def manacher(s):
            n = len(s)
            A, B = [], [1]*n
            mid, r = 0, 0
            for i in range(n):
                a = min(A[2*mid-i], r-i) if r>i else 0
                while i-a and i+a<n-1 and s[i-a-1]==s[i+a+1]:
                    a += 1
                    B[i+a] = max(B[i+a],a*2+1)
                A.append(a)
                if i+a>r:
                    mid, r = i, i+a
            return B    # B[i]: i结尾的最大回文子串长度(奇数)
        B = manacher( '#'+'#'.join(s)+'#')
        i = B.index(max(B))
        return s[(i-B[i]+1)//2:i//2]

时间 O(N),73 ms