本文深入剖析暴力递归解法导致内存超限的根本原因，介绍空间友好的动态规划实现，并提供可直接提交的 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 瓶颈的核心策略。
