LeetCode5题优化：最长回文子串高效解法

本文直击LeetCode第5题“最长回文子串”的核心痛点，深入揭示暴力递归+记忆化方案因递归深度过大、子问题重复爆炸和栈内存累积而导致内存超限（MLE）与递归错误的根源，并系统性地引出高效、稳健的动态规划解法——通过自底向上填表避免递归开销，以O(n²)时间复杂度和可优化至O(n)空间复杂度提供可直接AC的标准实现，助你彻底摆脱超时超限陷阱，真正掌握回文子串问题的最优解思维。

本文深入剖析暴力递归解法导致内存超限的根本原因，介绍空间友好的动态规划实现，并提供可直接提交的 O(n²) 时间、O(n²) 空间（可优化至 O(n)）标准解法。

本文深入剖析暴力递归解法导致内存超限的根本原因，介绍空间友好的动态规划实现，并提供可直接提交的 O(n²) 时间、O(n²) 空间（可优化至 O(n)）标准解法。

LeetCode 第5题“最长回文子串”看似简单，却极易陷入低效陷阱。你提供的递归+记忆化方案（dp(word[:-1]) 和 dp(word[1:])）在逻辑上试图枚举所有子串并缓存检查结果，但其递归树呈指数级爆炸增长：对长度为 n 的字符串，子串总数虽为 O(n²)，但该 DFS 会重复生成大量重叠子问题（如 "babad" 中 "aba" 可能被 dp("babad") → dp("baba") → dp("aba") 和 dp("babad") → dp("abad") → dp("aba") 两条路径多次触发），且 checked_words 集合仅去重输入字符串，无法剪枝中间冗余调用。更关键的是，Python 递归调用栈深度受限（默认约 1000 层），而该算法在最坏情况下递归深度可达 O(n)，极易触发 RecursionError 或因大量函数帧累积导致 Memory Limit Exceeded（MLE） —— 这正是你在长测试用例中遇到的问题。

相比之下，标准动态规划解法通过自底向上填表彻底规避递归开销，时间复杂度稳定为 O(n²)，空间复杂度可控。核心思想是定义二维布尔数组 dp[i][j] 表示子串 s[i:j+1] 是否为回文。状态转移方程简洁明确：

• 边界1（长度为1）：dp[i][i] = True
• 边界2（长度为2）：dp[i][i+1] = (s[i] == s[i+1])
• 一般情况（长度 ≥3）：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

以下为优化后的完整实现（含详细注释）：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s

        # dp[i][j] 表示 s[i:j+1] 是否为回文
        dp = [[False] * n for _ in range(n)]
        # 记录最长回文的起始索引和长度
        start, max_len = 0, 1

        # 所有长度为1的子串都是回文
        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
                start, max_len = i, 2

        # 枚举长度从3到n
        for length in range(3, n + 1):
            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
                    start, max_len = i, length

        return s[start:start + max_len]

✅ 关键优化点说明：

• 无递归调用栈：完全避免函数调用开销与栈溢出风险；
• 精确空间控制：二维 DP 表占用 O(n²) 空间（n=1000 时约 1MB），远低于递归方案的不可控内存增长；
• 早期剪枝：通过 start 和 max_len 实时记录最优解，无需存储所有子串；
• 线性扫描顺序：按子串长度升序填充，确保 dp[i+1][j-1] 总是已计算。

⚠️ 注意事项：

• 若需进一步压缩空间，可改用中心扩展法（O(n²) 时间，O(1) 空间）：遍历每个可能的回文中心（共 2n−1 个：n 个单字符中心 + n−1 个双字符中心），向两边扩展验证；
• 务必避免在循环内创建大量临时字符串（如 word[:-1]），这会引发频繁内存分配；
• LeetCode 对 Python 的内存限制严格（通常 ≤ 100MB），任何未加约束的集合/列表/递归都可能触雷。

总结而言，解决此类字符串 DP 问题，应优先选择迭代式状态转移而非深度优先搜索。理解子问题依赖关系、控制数据结构规模、杜绝隐式内存膨胀，是突破 MLE 瓶颈的核心策略。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《LeetCode5题优化：最长回文子串高效解法》文章吧，也可关注golang学习网公众号了解相关技术文章。