Leetcode 5. 最长回文子串
题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
解法1
动态规划，以
f(i,j)
表示字符串中下标
i
到
j
的字符串是否为回文串，包括首尾下标字符，若
![s[i]==s[j]](https://ask.qcloudimg.com/http-save/yehe-3177482/0baaggx11l.svg)
s[i]==s[j]
。则有：
f(i,j) = \begin{cases} True, & \text{ $j-i \lt 3$ }\\ f(i+1,j-1), & \text{ $j-i \ge 3$ } \end{cases}
借助二维数组记录
![flag[i][j]](https://ask.qcloudimg.com/http-save/yehe-3177482/55ai4yzavx.svg)
flag[i][j]
记录
f(i,j)
状态。
class Solution:
def longestPalindrome(self, s: str) -> str:
ret,flag='',[[False]*len(s) for i in range(len(s))]
for j in range(len(s)):
for i in range(j,-1,-1):
if s[i]==s[j]:
if j-i<3 or flag[i+1][j-1]:
flag[i][j]=True
ret=s[i:j+1] if j-i+1>len(ret) else ret
return ret解法2
解法1借助了二维数组空间来完成计算，这里优化数组空间为一维数组。
由解法1可知，对于下标
j-1
的一维数组空间
![flag[i][j-1]](https://ask.qcloudimg.com/http-save/yehe-3177482/snumbl9box.svg)
flag[i][j-1]
:
![flag[0][j-1],flag[1][j-1],flag[2][j-1]...flag[j-1][j-1]](https://ask.qcloudimg.com/http-save/yehe-3177482/j1c9zi2c3g.svg)
flag[0][j-1],flag[1][j-1],flag[2][j-1]...flag[j-1][j-1]
表示
![s[i][j-1] (0 \le i \le n-1)](https://ask.qcloudimg.com/http-save/yehe-3177482/sk9km50izi.svg)
s[i][j-1] (0 \le i \le n-1)
是否为回文串。
对于下标
j
的一维数组空间
flag[i][j]
，如果
s[i]==s[j]
，则
flag[i][j]
取决于
![flag[i+1][j-1]](https://ask.qcloudimg.com/http-save/yehe-3177482/ozf9l3l6h2.svg)
flag[i+1][j-1]
。这里可以使用一维数组
flag
记录状态，则
![flag[i]](https://ask.qcloudimg.com/http-save/yehe-3177482/s3dpzl7nh5.svg)
flag[i]
取决于
![flag[i+1]](https://ask.qcloudimg.com/http-save/yehe-3177482/pzndfa6k07.svg)
flag[i+1]
。
class Solution:
def longestPalindrome(self, s: str) -> str:
ret,flag='',[False]*len(s)
for j in range(len(s)):
for i in range(j+1):
if s[i]==s[j] and (j-i<3 or flag[i+1]):
flag[i]=True
ret=s[i:j+1] if j-i+1>len(ret) else ret
else:
flag[i]=False
return ret解法3
前面两种解法都需要
O(n^2)
的计算复杂度，解法3采用 manacher 算法，首先使用字符串中不存在的字符，扩充原始字符串，以此忽略奇数和偶数长度的影响。然后由左向右遍历字符串中元素，以每个元素为对称轴，扩散求回文串长度。
若是填充后进行常规的扩散求回文串，则复杂度依然是
O(n^2)
，manacher 算法中记录已访问回文串最右元素下标 maxrt，及当前的对称轴下标 cen。则继续访问时，若元素下标 i 在 maxrt 之前，根据对称性，以 i 位置为对称轴的回文串已全部访问，或已访问 s[i:maxrt+1] 部分，剩下的部分可继续访问。通过该方式避免了对每个下标位置的重复扩散访问，满足
O(n)
的计算复杂度。
class Solution:
def longestPalindrome(self, s: str) -> str:
s='#'+'#'.join(list(s))+'#'
ret,m,cen,maxrt='',[0]*len(s),0,0
for i in range(len(s)):
if i<maxrt:
m[i]=min(m[2*cen-i],maxrt-i)
while i-m[i]-1>=0 and i+m[i]+1<len(s) and s[i-m[i]-1]==s[i+m[i]+1]:
m[i]+=1
if i+m[i]>maxrt:
cen,maxrt=i,i+m[i]
if m[i]>len(ret):
ret=s[i-m[i]:i+m[i]+1].replace('#','')
return ret本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.05.15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读