题目描述

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

题解：动态规划

这是一道很经典的题目。首先我想到了动态规划算法：

对于子串s[i…j]，它为回文子串的条件为：s[i+1 … j-1]为回文子串，且s[i]==s[j]。想到这里，状态转移方程就已经显然易见了。

那么初始状态呢？我们的状态转移方程是从短的子串向长的子串转移的，因此外循环应该是子串长度。当子串长度为1，也就是只有一个字符时，显然为回文子串，这就是初始状态。

由于要返回最长的回文子串（SJ），因此需要记录一下。

该算法的时间复杂度为O(n²)，空间复杂度也是O(n²)。

两个关于Python语法的点

• 定义二维数组

dp = [[True for _ in range(n)] for _ in range(n)]

• 切片：切片结果不包括end_index！

代码一：动态规划（Python）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best_l, best_i = 0, 0
        if n < 2:
            return s
        dp = [[Fasle for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i] = True       
        for l in range(1, n):
            for i in range(n):
                if i + l < n:
                    dp[i][i+l] = s[i] == s[i+l] and dp[i+1][i+l-1] if l > 1 else s[i] == s[i+l]
                    if dp[i][i+l] and l > best_l:
                        best_i, best_l = i, l
        return s[best_i:best_i+best_l+1]

提交上述代码，发现TLE。下一步，在不改变算法时间复杂度的前提下，作语句优化（其实就是牺牲一定的可读性，换取更高的执行效率）：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best_l, best_i = 0, 0
        if n < 2:
            return s
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for l in range(1, n):
            for i in range(n):
                j = i + l
                if j < n:
                    if s[i] == s[j]:
                        if l == 1:
                            dp[i][j] = True
                        else:
                            dp[i][j] = dp[i+1][j-1]
                    if dp[i][j]:
                        best_i, best_l = i, l
        return s[best_i:best_i+best_l+1]

改进 修改后的代码是通过的。可以观察到，显然代码行数变多了。但对于机器执行来说，速度变快了。

进一步改进：分析状态转移路径

虽然到这里其实已经完事了，但对于动态规划算法来说，（或许）可以通过分析状态转移路径的方法作进一步空间优化。

两种分析思路：

• 正向（拓展）：
  dp[i][i]作为起点，只会决定dp[i-1][i+1]，下一步只会决定dp[i-2][i+2]，传递路径是单链的。
• 反向（递归）：
  dp[i][j]仅取决于dp[i+1][j-1]，下一步仅取决于dp[i+2][j-2]，传递路径同样是单链的。

因此，我们利用正向传递的单链性质，通过“拓展”的方式设计算法。需要注意的是，对于奇数长度与偶数长度的回文子串，它们的回文中心是不同的，需要分情况讨论。官方题解中有这样一句话：

我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。

这里的“拓展”，其实本质上还是动态规划。该算法共选择了n次扩展中心，每次至多扩展n次，因此时间复杂度为O(n²)。该算法没有占用额外的存储空间。这与“分析状态转移路径能够在保证时间不变的前提下优化空间”一致。

代码二：拓展法（Python）

    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        best_l, best_r = 0, 0
        for i in range(n):
            for delta in [0, 1]: # 分别讨论奇数长度与偶数长度
                l, r = i, i + delta
                while l >= 0 and r < n and s[l] == s[r]:
                    if r - l > best_r - best_l:
                        best_l, best_r = l, r
                    l, r = l-1, r+1
                l, r = i, i+1
        return s[best_l: best_r+1]