力扣第 5 题
题目
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s 仅由数字和英文字母组成
分析
#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