LeetCode-005：从中心扩散找最长回文子串，可行吗？

本题在线练习：LeetCode 5. 最长回文子串 - 在线练习（免费 · 无需登录 · AI 辅助）(https://onefly.top/zero2Leetcode/playground.html?id=5) 配套刷题网站 Zero2Leetcode —— 内置本地 OJ + AI 教练，零门槛开始刷 Hot 100。 题目概述 给定一个字符串 s，返回它的最长回文子串。 回文的定义：从左读和从右读一样，比如 aba、abba。 这题最容易走偏的点是：很多人一上来就想“枚举所有子串”，那是 O(n^3)，会超时。更自然的思路是：回文一定有一个“中心”，从中心向两边扩展即可。 核心思路：回文的“中心”只有两种 回文子串的中心位置： 奇数长度回文：中心是一个字符，例如 aba 的中心是 b 偶数长度回文：中心是两个字符之间的缝隙，例如 abba 的中心在两个 b 之间 因此只要枚举每个可能中心（2n-1 个），对每个中心做“左右扩散”，就能在 O(n^2) 内求解。 先从最自然的思路讲起：中心扩散 代码实现（中心扩散） class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n <= 1: return s def expand(l: int, r: int) -> tuple[int, int]: # 返回最长回文的左右边界（闭区间） while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 return l + 1, r - 1 best_l, best_r = 0, 0 for i in range(n): l1, r1 = expand(i, i) # 奇数回文 l2, r2 = expand(i, i + 1) # 偶数回文 if r1 - l1 > best_r - best_l: best_l, best_r = l1, r1 if r2 - l2 > best_r - best_l: best_l, best_r = l2, r2 return s[best_l:best_r + 1] 逐行拆解：expand 为什么“退一步”返回 expand(l, r) 的循环条件是“还能扩散且两侧字符相等”。当循环退出时，说明 (l, r) 这一对已经不合法了。 所以真正的回文边界要“退回一步”，即返回 l+1, r-1。 手动模拟：s = "babad" 取中心 i=1（字符 a）： 初始 (l,r)=(1,1)，匹配 a 扩散到 (0,2)，匹配 b 和 b 再扩散到 (-1,3) 越界，停止 返回 (0,2)，回文是 "bab"。 取中心 i=2（字符 b）则会得到 "aba"。两者长度一样，返回任意一个都符合题意。 进阶解法：动态规划（可选） 动态规划也能做，但比中心扩散更绕，通常不建议作为第一选择。 定义 dp[i][j] 表示 s[i..j] 是否是回文： 如果 s[i] != s[j]，则不是回文 如果 s[i] == s[j]，则需要 dp[i+1][j-1] 为真（或者长度小于等于 2 时天然成立） DP 的时间也是 O(n^2)，空间 O(n^2)。 复杂度分析 中心扩散： 时间：最坏 O(n^2)（每个中心最多扩散 O(n)） 空间：O(1) 总结 这题最重要的不是“记住代码”，而是形成一个直觉： 最长回文不是从“枚举子串”开始，而是从“枚举中心、向两边扩散”开始。 把奇数中心与偶数中心都处理到位，这题就稳定了。