LeetCode 5最长回文子串动态规划实现超时如何优化

我近期在练习LeetCode题目 5. Longest Palindromic Substring，题目要求如下：

给定字符串s，返回*s中的最长回文子串*。

我采用动态规划方法编写的代码在大型测试用例上始终触发时间超限错误，具体实现思路为：

• 状态定义：dp[(i, j)] = True表示区间s[i]到s[j]对应的子串是回文串
• 递推规则：若s[i] == s[j]且dp[(i+1, j-1)]为True，则s[i]到s[j]对应的子串也为回文串

当前实现代码如下：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = {}      
        res = ""
        
        for i in range(len(s)):
            # single character is always a palindrome
            dp[(i, i)] = True
            res = s[i]
        
        #fill in the table diagonally
        for x in range(len(s) - 1):
            i = 0
            j = x + 1
            while j <= len(s)-1:
                if s[i] == s[j] and (j - i == 1 or dp[(i+1, j-1)] == True):
                    dp[(i, j)] = True
                    if(j-i+1) > len(res):
                        res = s[i:j+1]
                else:
                    dp[(i, j)] = False
                i += 1
                j += 1

        return res

你的DP逻辑本身没有错误，理论时间复杂度为O(n²)，超时完全是实现层面的不必要开销导致的，核心问题有两点：

• 用元组作为键的字典存储DP状态，哈希表的键计算、读写开销远高于数组的下标直接访问，字符串长度较大时这部分开销会成为主要耗时来源。
• 每次找到更长回文就执行字符串切片生成新字符串赋值给结果，Python字符串是不可变对象，切片会触发新的内存分配和数据拷贝，频繁操作的开销极高；反复调用len(res)计算长度也存在不必要的消耗。

针对以上问题的优化手段：

1. 将字典存储DP状态替换为二维布尔数组，用n*n的二维列表即可，下标访问速度比字典快一个量级以上。
2. 不提前做切片保存结果，改用两个变量记录最长回文的起始下标和长度，所有状态遍历完成后仅执行一次切片返回结果。

优化后的DP实现参考：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        dp = [[False] * n for _ in range(n)]
        max_len = 1
        start = 0

        for i in range(n):
            dp[i][i] = True

        # 按子串长度从小到大遍历
        for length in range(2, n + 1):
            for i in range(n):
                j = i + length - 1
                if j >= n:
                    break
                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    dp[i][j] = True if j - i <= 2 else dp[i+1][j-1]
                
                if dp[i][j] and length > max_len:
                    max_len = length
                    start = i
        
        return s[start:start+max_len]

如果需要进一步提升性能，可以替换为中心扩展法，同样是O(n²)时间复杂度，但不需要维护二维状态数组，常数项更低；处理超大规模输入时可以使用Manacher算法，将时间复杂度降到O(n)。

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