Leetcode 5：最长回文子串（最详细的解法！！！）[通俗易懂]

全栈程序员-站长 • 2022年5月28日下午11:16 • 未分类 • 阅读 24

大家好，又见面了，我是你们的朋友全栈君。

给定一个字符串 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)$ 表示区间在 $[i, j]$ 内的字符串是不是回文串，其中i和j表示子串在s中的左右位置。

$f(i,j)=f(i+1,j-1)\ 当\ s_i=s_j时$

思考边界条件，当 $s_i=s_{j}$ 并且 $j = i + 1$ 的时候，此时字符串由两个相同字符构成；当 $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]