本文详解 leetcode 第 5 题“最长回文子串”的内存与时间双重优化方案，摒弃暴力递归+重复校验的低效思路，采用空间可控的二维 dp 方法，在 o(n²) 时间与 o(n²) 空间内稳定通过所有测试用例。
本文详解 leetcode 第 5 题“最长回文子串”的内存与时间双重优化方案，摒弃暴力递归+重复校验的低效思路，采用空间可控的二维 dp 方法，在 o(n²) 时间与 o(n²) 空间内稳定通过所有测试用例。
你提交的原始代码之所以触发 Memory Limit Exceeded（MLE），根本原因并非单次内存占用过高（如本地测得的 128MB），而在于递归调用栈深度失控 + 指数级子串生成 + 无剪枝的集合缓存。以长度为 n 的字符串为例，dp(s) 会递归生成 O(2ⁿ) 个子串（如 "abc" → "ab", "bc", "a", "b", "c"…），即使 checked_words 仅占 16MB，其存储的子串对象本身（含字符串副本、哈希开销）和递归帧叠加，极易在 LeetCode 严格内存限制（通常 ≤ 100MB）下崩溃——尤其面对题干中长达 1000+ 字符的极端输入。
更关键的是，该方法未利用回文的结构性质：一个长回文的内部子串往往也是回文（如 "abccba" 中 "bccb" 和 "cc" 均为回文）。因此，高效解法应基于自底向上动态规划，复用已有结果，避免重复计算与冗余存储。
✅ 推荐解法：二维 DP（空间/时间均衡，清晰易懂）
我们定义二维布尔数组 dp[i][j]，表示子串 s[i..j]（闭区间）是否为回文。状态转移依赖两个条件：
- 边界字符相等：s[i] == s[j]
- 内部子串是回文：dp[i+1][j-1] is True（当 j - i >= 2 时）
初始化需覆盖两种基础情形：
- 所有单字符子串：dp[i][i] = True
- 所有双字符子串：dp[i][i+1] = (s[i] == s[i+1])
随后按子串长度 L 从小到大枚举（3 → n），确保计算 dp[i][j] 时 dp[i+1][j-1] 已就绪。同时维护最长回文的起始索引与长度，避免频繁切片。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
# 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
# 枚举长度 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²)。若追求极致空间效率，可改用中心扩展法（O(1) 额外空间，O(n²) 时间），枚举每个可能的回文中心（共 2n−1 个：n 个单字符中心 + n−1 个双字符间隙中心），向两边扩展。
-
避免常见陷阱：
- 循环顺序必须按子串长度升序（而非随意遍历 i,j），否则 dp[i+1][j-1] 可能未计算；
- 边界判断要严谨（如 i+1
- 返回子串时使用 s[start:start+max_len]，而非重建字符串逻辑。
-
为什么你的 checked_words 无效？
即使去重，仍无法规避指数级递归调用栈（Python 默认递归深度约 1000，而 dp("a"*1000) 会产生远超此限的调用帧），且 word[:-1] 和 word[1:] 每次都创建新字符串对象，内存开销呈几何增长。
✅ 总结
解决回文类问题，核心是识别并利用重叠子问题。暴力递归虽直观，但在字符串场景下极易因子串爆炸和深层递归导致 MLE 或 TLE。动态规划通过显式状态定义与有序计算顺序，将时间复杂度控制在可接受的 O(n²)，并确保内存使用线性可预测。对于 LeetCode 第 5 题，此 DP 解法是平衡正确性、可读性与性能的最佳实践。
