最长回文子串：我的动态规划（DP）解法为何超时？

嘿，我来帮你拆解下为什么你的动态规划解法会超时，同时给你几个优化方向和更高效的替代方案～

先说说你的代码里拖慢速度的点 #

1. 动态列表append的额外开销 #

你初始化table的时候是每个元素都是一个只含True的列表，然后在循环里不断用table[j].append(...)来扩展。这种动态添加元素的操作在Python里其实是有额外开销的——每次append都可能涉及到列表内存的重新分配，当字符串很长时，这种累积的开销会很明显。

2. 循环逻辑不够高效，缺少提前终止 #

你的内层循环索引计算有点绕，而且没有利用当前已经找到的最长回文长度来做剪枝。比如，如果你已经找到了一个长度为max_len的回文，那后续所有长度小于等于max_len的子串其实都没必要再检查了，直接跳过就能节省不少时间。

3. DP表的访问方式不够直观 #

你的table[j][i-1]这种索引方式容易出错，而且Python对二维列表的访问虽然不算慢，但如果能更清晰地定义DP状态，也能减少一些隐性的开销。

优化后的DP解法 #

我们可以预先初始化一个固定大小的二维布尔数组，调整循环顺序，再加上剪枝逻辑，这样能明显提升效率：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s
        
        # dp[i][j] 表示 s[i..j] 这个子串是否是回文
        dp = [[False] * n for _ in range(n)]
        max_len = 1
        start_idx = 0
        
        # 单个字符肯定是回文
        for i in range(n):
            dp[i][i] = True
        
        # 先处理长度为2的子串
        for i in range(n - 1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                max_len = 2
                start_idx = i
        
        # 处理长度 >=3 的子串，length是子串的长度
        for length in range(3, n + 1):
            # 剪枝：如果当前要检查的长度不超过已找到的最长回文，直接跳过
            if length <= max_len:
                continue
            # i是子串的起始索引
            for i in range(n - length + 1):
                j = i + length - 1  # 子串的结束索引
                # 首尾字符相等，且中间的子串也是回文
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    max_len = length
                    start_idx = i
        
        return s[start_idx:start_idx + max_len]

更高效的替代方案：中心扩展法 #

其实对于最长回文子串问题，中心扩展法的实际运行效率比DP要高不少——它的时间复杂度同样是O(n²)，但不需要额外的O(n²)空间，而且常数项更小，没有DP表的初始化和访问开销：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        start, end = 0, 0
        
        def expand_around_center(left, right):
            # 向两边扩展，直到无法形成回文
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 返回回文的长度和起始索引
            return right - left - 1, left + 1
        
        for i in range(len(s)):
            # 处理奇数长度的回文（中心是单个字符）
            len_odd, start_odd = expand_around_center(i, i)
            # 处理偶数长度的回文（中心是两个字符之间）
            len_even, start_even = expand_around_center(i, i+1)
            
            current_max = max(len_odd, len_even)
            if current_max > end - start:
                if len_odd > len_even:
                    start, end = start_odd, start_odd + len_odd
                else:
                    start, end = start_even, start_even + len_even
        
        return s[start:end]

这个方法的核心思路很简单：遍历每个字符（以及每对相邻字符）作为回文的中心，向左右扩展，记录能扩展出的最长回文的起始和结束位置，最后返回对应的子串就行。

内容的提问来源于stack exchange，提问作者dmh