LeetCode 5. 最长回文子串
2019-02-20 本文已影响0人
liulei_ahu
5. 最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例2
输入: "cbbd"
输出: "bb"
解题思路
方法1 动态规划
定义dp[i][j]如下,
故
找到满足的最长的即为最终的结果
代码实现
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# dp
dp = [[False for i in range(len(s))] for j in range(len(s))]
str = ''
for i in range(len(s)): # 长度为1
dp[i][i] = True
str = s[i] # maxlen = 1
for i in range(0, len(s)-1): # 长度为2
if s[i] == s[i+1]:
dp[i][i+1] = True # maxlen = 2
str = s[i:i+2]
for i in range(2,len(s)):
for j in range(0,len(s)-i):
if s[j] == s[j+i] and dp[j+1][j+i-1]:
dp[j][j+i] = True # maxlen = i+1
str = s[j:j+i+1]
return str
时间复杂度为, 空间复杂度为
方法2 中心扩展算法
从字符串的中心分别向两侧查找,判断是否满足回文条件,需要注意的是奇偶长度的字符串的中心位置有所差异,如'aba'的中心为'b', 而'abba'的中心为两个'b'之间
代码实现
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# 中心扩展算法
def ismatch(self, s, l, r):
while(l>=0 and r<len(s) and s[l] == s[r]):
l = l - 1
r = r + 1
return r-l-1
l = 0
r = 0
for i in range(len(s)):
len1 = self.ismatch(s, i, i)
len2 = self.ismatch(s, i, i+1)
length = max(len1, len2)
if (length > r-l + 1):
l = i - (length-1)//2
r = i + length//2
return s[l:r+1]
时间复杂度为, 空间复杂度为
方法3 Manacher 算法
推荐一篇大牛的简书文章,里面介绍的Manacher算法较为易懂最长回文子串问题—Manacher算法, 补充一下没有解释的一点,为何RL[i]-1 即为原始串中以位置i为对称轴的最长回文串的长度?
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
s | # | c | # | a | # | b | # | a | # | c | # |
RL | 1 | 2 | 1 | 2 | 1 | 6 | 1 | 2 | 1 | 2 | 1 |
以上表为例,, 回文串长度为, 其中在该回文串中的个数比字母个数多1(在每个回文串中都有此规律), 所以原始串中的回文串长度为
代码实现
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# Manacher 算法
#预处理
s='#'+'#'.join(s)+'#'
RL=[0]*len(s)
MaxRight=0
pos=0
MaxLen = 0
index = 0
for i in range(len(s)):
if i<MaxRight:
RL[i]=min(RL[2*pos-i], MaxRight-i)
else:
RL[i]=1
#尝试扩展,注意处理边界
while i-RL[i]>=0 and i+RL[i]<len(s) and s[i-RL[i]]==s[i+RL[i]]:
RL[i]+=1
#更新MaxRight,pos
if RL[i]+i-1>MaxRight:
MaxRight=RL[i]+i-1
pos=i
if RL[i] > MaxLen:
index = i
MaxLen = RL[i]
return s[index-MaxLen+1:index+MaxLen-1].replace('#', '')
时间复杂度为, 空间复杂度为