Leetcode 5：最长回文子串（最详细的解法！！！）[通俗易懂]
Leetcode 5：最长回文子串（最详细的解法！！！）[通俗易懂]
大家好，又见面了，我是你们的朋友全栈君。
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。示例 2：
输入: "cbbd"
输出: "bb"解题思路
首先最简单的做法就是暴力解法，通过二重循环确定子串的范围，然后判断子串是不是回文，最后返回最长的回文子串即可。
class Solution:
def longestPalindrome(self, s):
""" :type s: str :rtype: str """
max_len, result = float("-inf"), ""
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
if s[i:j] == s[i:j][::-1]:
if j-i > max_len:
max_len = j-i
result = s[i:j]
return result我们直接跳过它QAQ。这个问题可以通过动态规划来解，定义函数 f ( i , j ) f(i,j) f(i,j)表示区间在 [ i , j ] [i,j] [i,j]内的字符串是不是回文串，其中i和j表示子串在s中的左右位置。
- f ( i , j ) = f ( i + 1 , j − 1 ) 当 s i = s j 时 f(i,j)=f(i+1,j-1)\ 当\ s_i=s_j时 f(i,j)=f(i+1,j−1) 当 si=sj时
思考边界条件，当 s i = s j s_i=s_{j} si=sj并且 j = i + 1 j=i+1 j=i+1的时候，此时字符串由两个相同字符构成；当 i = j i=j i=j的时候，此时字符串由单个字符构成。
class Solution:
def longestPalindrome(self, s):
""" :type s: str :rtype: str """
if not s:
return ""
s_len = len(s)
mem = [[0]*s_len for _ in range(s_len)]
left, right, result_len = 0, 0, 0
for j in range(s_len):
for i in range(j):
if s[i] == s[j] and (j-i < 2 or mem[i+1][j-1]):
mem[i][j] = 1
if mem[i][j] and result_len < j-i+1:
result_len = j - i + 1
left, right = i, j
mem[j][j] = 1
return s[left:right+1]这种算法的时间复杂度是O(n^2)，空间复杂度也是O(n^2)。有没有更好的做法呢？
我们知道回文串是中心对称的，所以只要找到回文串的中心，然后向两边扩展即可。这里的中心位置我们要奇偶分开考虑，如果字符串长度是奇数的话，中心就只有一个元素；如果字符串是偶数的话，那么中心是两个元素。
class Solution:
def longestPalindrome(self, s):
""" :type s: str :rtype: str """
if not s or len(s) < 1:
return ""
def expandAroundCenter(left, right):
L, R = left, right
while L >= 0 and R <len(s) and s[L] == s[R]:
L -= 1
R += 1
return R - L - 1
left, right = 0, 0
for i in range(len(s)):
len1 = expandAroundCenter(i, i) # 奇数
len2 = expandAroundCenter(i, i+1) # 偶数
max_len = max(len1, len2)
if max_len > right - left:
left = i - (max_len - 1)//2
right = i + max_len//2
return s[left:right+1]还有一种思路也非常不错，可以先确定回文串的右边界i，然后以右边界i向左找回文串。假设在i之前的最长回文子串长度是l，此时我们需要分别检查i+1左侧字符串长度为l+2和l+1子串是不是回文串。如果l+2是回文串，那么字符串的最大长度变成l+2，对于l+1同理。
代码如下：
class Solution:
def longestPalindrome(self, s):
""" :type s: str :rtype: str """
if len(s) < 2 or s == s[::-1]:
return s
start, maxlength = 0, 1
for i in range(1, len(s)):
odd = s[i-maxlength-1:i+1] # 检查l+2
even = s[i-maxlength:i+1] # 检查l+1
if i-maxlength-1 >= 0 and odd == odd[::-1]:
start = i-maxlength-1
maxlength += 2
elif i-maxlength >= 0 and even == even[::-1]:
start = i-maxlength
maxlength += 1
return s[start:start+maxlength]通过maxlength我们过滤了许多不必要的重复计算，所以这个代码的效率比前面一个要快许多。
这样我们的空间复杂度就优化到了常数级别。有没有更快的算法呢？有，使用Manacher算法，类似的思想在KMP算法中也有应用。
我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题，希望大家指出！！！
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/139935.html原文链接：https://javaforall.cn
腾讯云开发者
