本文深入剖析 leetcode 第 5 题“最长回文子串”中常见的内存超限（mle）问题，揭示递归+暴力回溯解法的隐式空间爆炸根源，并系统讲解基于二维 dp 的 o(n²) 时间、o(n²) 空间（可优化至 o(n)）的稳定实现方案。
本文深入剖析 leetcode 第 5 题“最长回文子串”中常见的内存超限（mle）问题，揭示递归+暴力回溯解法的隐式空间爆炸根源，并系统讲解基于二维 dp 的 o(n²) 时间、o(n²) 空间（可优化至 o(n)）的稳定实现方案。
你提供的原始代码看似简洁——通过递归拆分字符串（word[:-1] 和 word[1:]），配合 is_palindrom() 检查并用 set 去重，逻辑上确实能穷举所有子串。但正是这种“看似合理”的设计，在 LeetCode 的严格评测环境下触发了 Memory Limit Exceeded。根本原因不在于单次内存占用（如本地测得的 128MB），而在于递归调用栈深度 + 子串对象数量 + 哈希集合开销三者叠加产生的指数级隐式空间增长。
以输入字符串长度为 $n$ 为例：
- 每次 dp(word) 调用生成两个新子串（word[:-1] 和 word[1:]），形成一棵二叉递归树；
- 该树节点总数高达 $O(2^n)$ 级别（即使去重，checked_words 中仍会存入大量中间子串，如 "babad" → "baba", "abad", "bab", "aba", "bad", ...）；
- Python 中每个字符串是不可变对象，word[1:] 等切片操作会创建全新副本，而非视图；长度为 $k$ 的子串约占用 $k$ 字节，海量短串累积内存远超预期；
- 同时，递归深度可达 $n$，每层栈帧保存局部变量和返回地址，进一步加剧栈内存压力。
因此，本地测试未报错，是因为你的环境允许更高内存上限或未触发最坏-case；而 LeetCode 对单个测试用例的内存有硬性限制（通常 ≤ 100MB），且该长字符串（> 300 字符）恰好使递归树规模突破阈值。
✅ 正确解法应摒弃“生成所有子串再验证”的思路，转而采用动态规划（DP）预处理回文状态，实现时间与空间的可控性：
核心思想：区间 DP 判断回文
定义二维布尔数组 dp[l][r]，表示子串 s[l:r+1] 是否为回文。利用回文的结构性质：
- 单字符必为回文：dp[i][i] = True
- 双字符回文当且仅当两字符相等：dp[i][i+1] = (s[i] == s[i+1])
- 长度 ≥ 3 时：dp[l][r] = (s[l] == s[r]) and dp[l+1][r-1]
这样，我们只需按子串长度从小到大枚举，确保计算 dp[l][r] 时 dp[l+1][r-1] 已被计算，避免递归与重复计算。
以下是优化后的标准 DP 实现：
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
# dp[l][r] 表示 s[l:r+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
# 枚举长度 l 从 3 到 n
for l in range(3, n + 1):
for i in range(n - l + 1):
j = i + l - 1 # 子串右边界
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start, max_len = i, l
return s[start:start + max_len]关键优势与注意事项：
- ✅ 时间复杂度稳定为 $O(n^2)$：双重循环覆盖所有 $O(n^2)$ 个子串，每次状态转移 $O(1)$；
- ✅ 空间复杂度 $O(n^2)$：虽需二维数组，但对 $n \leq 1000$，最多分配 $10^6$ 个布尔值（约 1MB），远低于内存限制；
- ⚠️ 避免切片创建新字符串：全程使用索引 i, j 操作原字符串，零额外字符串对象；
- ⚠️ 无需哈希集合去重：DP 表天然按结构遍历，无冗余子串生成；
- ? 进阶优化（空间压缩）：若追求极致空间效率，可改用中心扩展法（$O(n^2)$ 时间，$O(1)$ 空间），或滚动数组优化 DP 至 $O(n)$ 空间（因 dp[l][r] 仅依赖 dp[l+1][r-1]，可按长度倒序更新一维数组）。
总结
解决 LeetCode MLE 问题，不能只看“当前内存用量”，更要分析算法的空间增长阶数与对象生命周期。本题中，递归分治的指数级分支 + 字符串切片副本 + 哈希集合膨胀，共同导致隐式内存失控；而区间 DP 通过状态复用与索引化操作，将空间消耗控制在多项式级别，兼顾正确性、效率与工程鲁棒性。掌握这种“从暴力到结构化预处理”的思维跃迁，是攻克高频动态规划题的关键能力。
