LeetCode_5_中等_最长回文子串

---

1. 题目

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：“bb”

---

提示：

• $1<=s.length<=1000$
• 仅由数字和英文字母组成

2. 思路及代码实现（Python）

2.1 动态规划

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 a(xxxx)a，如果我们已经知道中间部分的字符 (xxxx) 是回文串，那么 a(xxxx)a 一定是回文串，这是因为它的首尾两个字母都是 a。根据这样的思路，我们就可以用动态规划的方法解决本题。我们用 $P(i,j)$ 表示字符串 s 的第 i 到 j 个字母组成的串是否为回文串，可以得到状态转移 $P(i,j)=P(i+1,j?1)\wedge (S_i==S_j)$，循环终止的边界条件是 $i>j$ 或者 $S_i\ne S_j$，这里 $i==j$ 时显然是个最短的回文串，此时可以得到 $P(i,i)=True,P(i,i+1)==(S_i?S_{i+1})$，此时，若回文串扩展的两边字符不相等，则可以跳出这个回文串的扩展，可以得到当前子串的长度 $j?i+1$ 。

动态规划的方法需要存储一张 $n\times n$ 的表，通过存储之前计算过的值（状态），来节省后续计算的时间。单次循环的复杂度为 $O(1)$，状态转移总次数 $O(n^2)$，因此时间复杂度为 $O(n^2)$，空间复杂度也为 $O(n^2)$。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始，先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

执行用时：3024 ms
消耗内存：24.70 MB

参考来源：力扣官方题解

2.2 中心扩展算法

上述方法遍历了所有的长度，以及所有的左起始节点。但其实根据上述的状态转移公式可知，当一个子串为回文子串时，其内部子串也同样是回文子串，因此我们不必搜索所有的子串情况，而是可以只总最短的回文子串为中心进行扩展搜索，当扩展的两边字符不相等时，则停止搜索，依次遍历所有的最短子串中心。

显然，最短子串中心就是每个单独的字符串。这里的时间复杂度为 $O(n^2)$，遍历了长度为 1,2 的回文中心，并且每个中心向外最多扩展 $n//2$ 次，而空间复杂度为 $O(1)$，仅保存了最短回文中心和扩展的长度。

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

执行用时：300 ms
消耗内存：16.98 MB