LeetCode 5 最长回文子串：从暴力到中心扩展与动态规划

不想花里胡哨，直接说结论：最长回文子串这道题，是 LeetCode 第 5 题，也是我刷题生涯中遇到的第一道“标准 DP 入门题”，更是很多人面试时被问到手心冒汗的经典题。它表面上是求一个字符串里的最长回文片段，实际上考的是你对“枚举中心”和“状态转移”这两种底层思维的理解。这篇文章不打算给你堆一个标准答案，而是把我自己从暴力解法一路走到中心扩展法、动态规划法的完整思路和踩坑记录分享出来。无论你是刚开始刷 LeetCode 的萌新，还是准备面试想巩固字符串题型的同学，这篇都能给你一点实在的东西。

先说清楚它解决了什么问题：给定一个字符串s，要求返回其中最长的回文子串。所谓回文，就是正着读和倒着读都一样，比如"aba"、"abba"。题目看似简单，但字符串长度最长能到 1000，暴力枚举所有子串再判断回文，复杂度是 O(n³)，在 LeetCode 上直接超时。所以必须引入更聪明的算法。中心扩展法用 O(n²) 时间、O(1) 空间干净利落地解决；动态规划法同样用 O(n²) 时间，但用一个二维 DP 表换回了清晰的递推逻辑。两种解法各有特点，都值得吃透。

1. 题目理解与整体思路拆解

1.1 回文串的本质：对称性

回文串的核心就是对称。"racecar"之所以是回文，是因为从中间劈开，左右两边互为镜像。这个最简单的观察，直接引出了两种经典解法。

你仔细想：一个回文串去掉头尾两个字符后，剩下的中间部分仍然是回文。比如"ababa"去掉首尾的'a'后变成"bab"，依然是回文。这个性质看起来平凡，但它是动态规划法的根基，也是暴力法优化的切入点。

另一方面，如果从一个中心向两边扩展，只要两边字符相等，就能维持回文性质。这个观察不依赖“子结构”，而是依赖“生长过程”，这就是中心扩展法的灵魂。

所以这道题看起来是“求最值”，实际上考察的是你能不能抓住“对称性”这个几何直觉。

1.2 为什么暴力解法不可行

很多人第一反应是三层循环：枚举所有起点i、终点j，再判断s[i:j]是否是回文。

# 暴力解法示例，仅用于理解，切勿提交 def longestPalindrome_brutal(s: str) -> str: n = len(s) if n < 2: return s max_len = 1 begin = 0 for i in range(n - 1): for j in range(i + 1, n): if j - i + 1 > max_len and s[i:j+1] == s[i:j+1][::-1]: max_len = j - i + 1 begin = i return s[begin:begin + max_len]

这代码能跑，但n=1000时子串数量约 50 万个，每个判断回文又要 O(n) 时间，总计算量是 5 亿量级。在 LeetCode 的计时环境下，基本等不到结果。

更重要的不是超时，而是这种写法没有利用到回文的“重复结构”。每次判断s[i:j]是否回文，都要从头到尾重新比对，可其实"abcba"回文这个信息，在判断"b"是否回文时就已经隐含了。我们要做的就是把这些隐含信息利用起来。

1.3 两种高效解法的差异化选型

这道题最主流的两个高效解法是中心扩展法和动态规划法，它们走的路子完全不同：

• 中心扩展法：从每一个可能的“回文中心”出发，向两侧扩展，直到不能扩展为止。它不关心子问题之间的重叠，而是枚举所有可能的对称轴，直接模拟回文的生长过程。
• 动态规划法：定义dp[i][j]表示s[i:j+1]是否为回文，然后通过状态转移方程递推。它把回文判断拆成小规模子问题，用空间换时间。

选哪个更好？面试中这两种解法都会被认可。但从实际代码量和理解难度来看，中心扩展法更易上手；从体现算法思维层次来看，动态规划法更能展示你对状态定义的敏感性。我个人建议两个都掌握，因为面试官可能会让你“换一种思路再写一遍”。

2. 中心扩展法详解：从对称轴开始生长

2.1 核心思想：奇数长度与偶数长度的统一

回文的中心可能是一个字符，也可能是两个字符之间的空隙。比如"aba"的中心是字符'b'；而"abba"的中心是中间的两个'b'之间的空隙。

因此，中心扩展法需要枚举两类中心：

• 奇数长度回文的中心：单个字符，下标i。
• 偶数长度回文的中心：两个相邻字符之间的空隙，对应两个下标i和i+1，要求这两个字符相同才可能构成回文。

例如对字符串"aaaa"，枚举中心时：

• 单字符中心i=1（字符'a'），向两侧扩展得到"aba"?不，是"aaa"（因为索引0和2都是'a'），再扩展越界，得到长度3。
• 双字符中心(i=1, i+1=2)，字符都为'a'，扩展得到"aaaa"，长度4。

这就是为什么中心扩展法代码里经常出现两个循环：expand(s, i, i)和expand(s, i, i+1)。

2.2 扩展逻辑与边界控制

扩展函数的核心是：定义左右指针left和right，只要它们不越界，并且s[left] == s[right]，就继续向两边移动。一旦不满足条件，就停止，返回当前回文长度。

def expand_around_center(s: str, left: int, right: int) -> int: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 # 循环退出时，[left+1, right-1] 才是回文区间 return right - left - 1

这里最容易出错的是返回长度的计算。以s = "aba"，中心left = right = 1为例：

• 初始左右指针都在'b'上，s[1]==s[1]，移动后left=0, right=2。
• s[0]==s[2]，移动后left=-1, right=3。
• 越界退出，此时回文区间是[0, 2]，长度是2 - 0 + 1 = 3。
• 用公式right - left - 1得到3 - (-1) - 1 = 3，正确。

换成"abba"，中心left=1, right=2时，扩展过程同理，最终返回长度 4。

这个返回长度公式right - left - 1为什么这样写？因为在循环结束前最后一次成功扩展后，左右指针又各自向外走了一步，所以真正回文区间的左右边界是left+1和right-1，长度为(right-1) - (left+1) + 1 = right - left - 1。很多新手一上来写成right-left+1，结果错误百出。

2.3 完整代码与复杂度分析

def longestPalindrome(s: str) -> str: if not s or len(s) < 1: return "" start = 0 max_len = 1 def expand_from_center(left: int, right: int) -> int: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return right - left - 1 for i in range(len(s)): # 奇数长度回文中心 len1 = expand_from_center(i, i) # 偶数长度回文中心 len2 = expand_from_center(i, i + 1) cur_len = max(len1, len2) if cur_len > max_len: max_len = cur_len # 根据回文长度计算起始位置 start = i - (cur_len - 1) // 2 return s[start:start + max_len]

复杂度：

• 时间复杂度 O(n²)：每个中心最多扩展 O(n) 次，共有2n-1个中心（n 个单字符中心 + n-1 个双字符中心），因此总复杂度 O(n²)。
• 空间复杂度 O(1)：只用常数个变量，不额外开销。

对比暴力法的 O(n³)，中心扩展法是质变。这也是 LeetCode 上大多数用户提交的解法风格——短小精悍，击败 99% 不是问题。

2.4 为什么中心扩展比暴力优？

暴力法判断每个子串时，都要从两端向中间扫描，产生大量重复比较。例如判断"ababa"和"baba"和"aba"的回文性质时，重叠部分"aba"被反复比较。

中心扩展法则把每个中心独立对待，虽然不同中心之间也有重复比较，但每个中心向外扩展的过程是单调且不回溯的，它充分利用了“回文向外生长”这一动态过程。你可以把暴力法想象成“摄影师给每个子串单独拍照”，而中心扩展法是“从中心点向外拉镜头，一镜到底”，效率自然高不少。

这种优化思路在字符匹配类题目中很常见：与其反复判断整体，不如找到对称轴，顺着对称性走。

3. 动态规划法详解：用表记住答案

3.1 状态定义的由来

动态规划法的核心问题是：我怎么用一个二维表格把子串的回文性质存下来？

定义dp[i][j]为布尔值，表示子串s[i:j+1]（即从 i 到 j 的闭区间）是否为回文。显然，单个字符s[i:i+1]一定是回文，所以dp[i][i] = True。

那么dp[i][j]怎么从前面的状态转移过来？

观察回文性质：如果s[i] == s[j]，那么s[i:j+1]是否为回文取决于内部子串s[i+1:j]是否为回文，即dp[i][j] = dp[i+1][j-1]。

但有个前提：内部子串要存在。如果s[i:j+1]的长度小于等于2，比如"aa"、"ab"，此时只要s[i] == s[j]，它就是回文（空串和单字符天然是回文）。所以需要单独处理长度 2 的情况。

更严谨地说，当j - i < 2时，只要两端字符相等，dp[i][j] = True；当j - i >= 2时，要依赖dp[i+1][j-1]。

3.2 状态转移方程与初始化

整理成公式：

• 如果s[i] != s[j]，则dp[i][j] = False。
• 如果s[i] == s[j]：
  • 若j - i <= 2，则dp[i][j] = True（对应长度为1、2、3的字符串，长度3时如"aba"，两端相等，中间单字符天然回文）。
  • 否则dp[i][j] = dp[i+1][j-1]。

初始条件：每个单字符子串都是回文，即dp[i][i] = True。

这里我插一句，很多教材会把j - i <= 2写成j - i < 3，意思是当子串长度小于等于 3 时，只需要看两端。因为长度为 2（如"aa"）和长度为 3（如"aba"）时，内部不需要任何回文信息，这一细节非常关键。

3.3 填表顺序的坑：按长度从小到大

动态规划不是随便填表的，必须保证计算dp[i][j]时，dp[i+1][j-1]已经被计算过。

dp[i+1][j-1]所代表的子串长度为(j-1)-(i+1)+1 = j-i-1，比当前的j-i+1小 2。因此如果按子串长度从短到长递增来填表，就能保证依赖关系正确。

典型代码：

def longestPalindrome_dp(s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start = 0 max_len = 1 for i in range(n): dp[i][i] = True # L 表示子串长度，从 2 开始枚举 for L in range(2, n + 1): for i in range(n - L + 1): j = i + L - 1 if s[i] != s[j]: dp[i][j] = False else: if L <= 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and L > max_len: max_len = L start = i return s[start:start + max_len]

我强烈建议你在本地跑一下这段代码，用"babad"、"cbbd"、"a"、"ac"这几个用例验证。跑完你会发现dp表里从对角线开始向右上方向逐层填充，非常直观。

3.4 复杂度分析：空间换时间的典型案例

• 时间复杂度 O(n²)：两层循环，外层长度 L，内层起始位置 i。
• 空间复杂度 O(n²)：需要一个 n×n 的布尔矩阵。

当n=1000时，n²=1e6，每个布尔值在 Python 中实际占用约 28 字节（因为 Python 的 bool 是对象），完整矩阵会占用 28MB 左右，还能接受。但n=5000时就是 140MB，很可能会被内存限制卡住。这就是动态规划法的局限性。

相比之下，中心扩展法空间 O(1)，适用范围更广。如果你刷 LeetCode 时发现内存超限，多半就是动态规划方法在长字符串上的实现不够优化。

4. 双解法对比：时间、空间、适用场景

4.1 性能实测对比

我拿同一台机器、同一个 Python 3.10 环境测过这两种解法，测试字符串是长度 1000 的全'a'字符串（最极端情况，所有子串都是回文）。

动态规划法在同复杂度下为什么比中心扩展慢这么多？因为填表需要遍历所有i, j组合，Python 的双层循环开销大；而中心扩展法虽然最坏情况也是 O(n²)，但对全'a'这样的字符串，每个中心扩展的长度是 O(n)，平均总操作数其实也是 n² 量级，只不过每次操作只是简单的字符比较和指针移动，没有二维数组的索引和写入开销。

4.2 面试时怎么选？

面试官通常不会强制你用某一个，但你的选择会影响后续追问的方向。

• 如果你先写了中心扩展法，面试官大概率会追问“你能用动态规划做吗？”这正是展示你掌握多种思路的机会。
• 如果你先写了动态规划法，面试官可能追问“空间能优化吗？”你可以回答：用中心扩展法可以优化到 O(1)，或者用滚动数组保存上一行状态，但回文判断的依赖是斜向的，滚动数组不好直接套，所以更优雅的答案是中心扩展。

我个人的建议是：面试时先口头分析两种解法，然后主动说“我先用中心扩展法写一个 O(1) 空间的版本，再用动态规划法补充”。这样既展示了复杂度分析能力，又展示了代码实现能力。

4.3 除了这题，这些思路还能用在哪里？

中心扩展法不仅仅用于这一题。比如 LeetCode 第 647 题“回文子串”就是直接套中心扩展或 DP；第 516 题“最长回文子序列”用另一种 DP 思路；还有“最长回文子序列”在动态规划中依赖dp[i+1][j-1]的斜向转移，和本题如出一辙。

动态规划法的填表顺序“按长度从小到大”，也是一类经典问题的模板。刷题多了你会发现，区间 DP 类的题目（比如石子合并、多边形三角剖分）都是这个套路：外层枚举区间长度，内层枚举起点，再用一个状态转移方程把小区间组合成大区间。

所以这道题不是刷过就完了，它背后是两种算法思想的“样板间”，值得反复咀嚼。

5. 实战踩坑与排查技巧

5.1 边界条件：空串、单字符、无回文

题目保证了s至少为 1，但你还是要有防御性编码习惯。空串直接返回空串，长度为 1 直接返回本身，这两行代码能省掉很多后续麻烦。

最容易忽略的是“没有长度大于 1 的回文子串”的情况。比如s = "abc"，最长回文子串可以是任意单个字符，返回"a"、"b"、"c"都是合法的。因此 max_len 初始值应设为 1，start 初始值设为 0，这样循环结束直接返回s[0]也没问题。

5.2 中心扩展法的起止下标计算

在中心扩展法的代码里，更新 start 时用了这个公式：

start = i - (cur_len - 1) // 2

这个公式很多人不理解。我来推导一下。

已知回文中心的下标是i（或i和i+1之间的空隙），回文长度为cur_len。对于奇数长度，中心字符在整个回文中的位置就是正中间，左侧长度是(cur_len - 1) // 2，所以起点是i - (cur_len - 1) // 2。

对于偶数长度，中心是两个字符的间隙，左侧字符数是cur_len // 2。在代码里，统一用(cur_len - 1) // 2是否成立？验证一下：cur_len=4时，(4-1)//2 = 1，而正确的左侧字符数是 2，起点应为i - 1，那岂不是错了？

这里的关键在于：当偶数长度时，我们的中心是(i, i+1)，代码里 i 是左中心字符。如果回文长度为 4，左侧字符数是 2，正确起点是i - 1。但公式i - (cur_len - 1) // 2给出i - 1，是对的？不对，(4-1)//2 = 1，所以是i-1，正确。但如果是cur_len=6，左侧字符数应该是 3，公式(6-1)//2 = 2，给出i-2，实际应该是i-3？我们来验证。

假设回文长度为 6，中心是(i, i+1)，回文区间为[i-2, i+3]还是[i-3, i+2]？设两个中心字符分别为索引 1 和 2，长度为 6 的回文如"abccba"，中心是(2,3)，区间是[0,5]，左侧从 0 到 2 是 3 个字符，所以起点是i - 3。而(6-1)//2 = 2，不对。

我重新审视常见写法。LeetCode 官方 Python 题解中，使用的是：

start = i - (len1 - 1) // 2

其中i是单字符中心时，所以公式没问题。但我的代码里用了i作为循环变量，同时对 len1 和 len2 都使用同一个 i，这就有问题。实际上，在偶数中心时，左中心是i，右中心是i+1，回文起点应为i - (cur_len // 2 - 1)=i - cur_len // 2 + 1（因为左侧字符数等于cur_len // 2，而左中心本身是第1个左侧字符？等一下，推导清楚）。

设偶数回文为s[left..right]，中心空隙在m和m+1之间（m是左中心索引）。回文长度len = right - left + 1，且从左中心 m 向左扩展了 k 步，即left = m - k，从右中心 m+1 向右扩展了 k 步，即right = m + 1 + k。所以长度len = (m + 1 + k) - (m - k) + 1 = 2k + 2，左侧字符数是k+1=len / 2。

代码中用i代表 m，即中心左下标，那么起点left = i - k。因为k = len/2 - 1，所以left = i - (len/2 - 1) = i - len/2 + 1。

对于奇数回文，中心 m，左侧扩展 k 步，起点left = m - k，长度len = 2k+1，k = (len-1)/2，起点 = m - (len-1)/2。

所以对于同一个i代表 m（奇数中心）或左中心（偶数中心），不能用一个公式。

但很多代码确实用了start = i - (max_len - 1) // 2，这是怎么回事？是因为它们只更新start时，用的是以i为中心的最长回文长度len1和len2中的哪一个？有些代码是先分别计算 len1 和 len2，然后取较大者，再根据是奇数中心还是偶数中心来更新 start。但常见的 LeetCode 讨论区版本是：

for i in range(len(s)): len1 = expand(i, i) len2 = expand(i, i + 1) len = max(len1, len2) if len > end - start: start = i - (len - 1) // 2 end = i + len // 2

这个代码在偶数长度时也是统一用(len-1)//2和i + len//2，为什么正确？让我们用上面推导用这个场景验证。偶数长度 len=4，中心左下标 i，正确起点是 i - 1。公式i - (4-1)//2 = i - 1，正确。刚才我例子中 len=6 时，公式i - (6-1)//2 = i - 2，但正确应该是 i - 3，难道这段代码错了？等等，重新验证 len=6 的情况正确的end = i + len//2 = i+3，那回文区间就是 [i-2, i+3]，长度 6？计算一下长度：从 i-2 到 i+3 共 6 个字符，中心在哪？中心是两个字符，左中心是 i-1？不对，回文中心应该是区间中心。对于区间 [i-2, i+3]，中心空隙在 (i-1) 和 i 之间？因为区间长度 6，中间两个字符下标是 i-2+2 = i 和 i+1？实际上长度 6 的区间 [left, left+5]，中间两个字符是 left+2 和 left+3。若 left = i-2，中间两个字符是 i 和 i+1。所以左中心是 i，确实代码里的 i 是左中心，起点 i-2，公式给出 i-2，结果是正确的。我之前错误地认为“左中心是 m，起点 = m - 3”，是把左中心当成了中间两个字符中的第一个，但如果左中心是 i，则中间两个字符是 i 和 i+1，那么回文区间必然以 i 和 i+1 为对称中心，左右各扩展相同步数。长度 6 意味着左右各扩展 2 步？不对：左右各扩展 k 步时长度 = 2k+2，k=2 时长度 = 6，起点 = i - 2。对！我搞错了，长度 6 且以 (i,i+1) 为中心时，左侧是 i-2, i-1, i 共3个，右侧是 i+1, i+2, i+3 共3个，起点 i-2 = i - (6/2 - 1) = i - 2。正确。公式(len-1)//2 = (6-1)//2 = 2，也正确。所以统一公式在偶数时也成立！因为(2k+2 - 1)//2 = (2k+1)//2 = k（整除），而正确起点是 i - k。整数除法巧合般统一了。同样end = i + len//2，偶数时 = i + k+1，正确。奇数时 len=2k+1，(len-1)//2 = k，len//2 = k，区间 [i-k, i+k]，正确。

我之前推导里以为偶数 k = len/2 - 1，而起点 i - k；然后(len-1)//2= ? 算一下 len=6，k=2，len/2 - 1=2，起点 i-2，(6-1)//2=2，所以一致。数学上：len/2 - 1 与 (len-1)//2 在偶数 len 时是否相等？len=2k+2，len/2 -1 = k， (len-1)//2 = (2k+1)//2 = k。是的。所以公式是对的。我之前拿“左侧字符数 = len/2 = 3”却写成起点 i-3，错误在于左侧字符数包括中心本身，起点从第一个左侧字符到左中心前的距离是 len/2 - 1 = 2，所以起点 i-2。

因此这个公式其实是统一且正确的，不过还是要小心解释。

所以代码没问题。我在博文中会澄清这一点，避免很多人困惑。

5.3 动态规划表中的布尔值陷阱

Python 中创建n*n的二维列表时，很多人会写dp = [[False] * n] * n，这会导致每一行引用同一个列表，修改一行全变。正确做法是用列表推导式：

dp = [[False] * n for _ in range(n)]

这个坑我见过太多次了，尤其是从 C++/Java 转过来的朋友，总觉得[[False]*n]*n已经生成了一个矩阵，实际上它只是复制了引用。

5.4 死循环与越界

中心扩展时，如果忘记在循环里移动指针，就会死循环。建议在 while 循环体内部先判断、后移动，并保证每次循环至少移动一个指针。我习惯把越界检查放在前面，利用 Python 的短路求值，避免索引错误。

动态规划法里，内层循环for i in range(n - L + 1):很容易写错边界。可以手动模拟一下：当L=2，n=5时，range(4)产生 i=0..3，j=1..4，覆盖所有长度为2的子串，正确。

5.5 回文子串与回文子序列的混淆

很多人在刷完第 5 题后去刷第 516 题“最长回文子序列”，发现动态规划的状态定义几乎一样，但转移方程完全不同。回文子串要求连续，回文子序列不要求连续。第 516 题的转移是：

if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

一定要分清“子串”和“子序列”的区别。面试时如果你能主动提一句“如果题目改成子序列，转移方程就要变化”，会显得你思路开阔。

6. 从这道题延伸出去的几个想法

6.1 Manacher 算法有必要学吗？

这道题还有一个线性时间的至尊解法：Manacher 算法（马拉车算法），时间复杂度 O(n)。很多刷题指南会推荐学习它，因为它是字符串处理中一个非常巧妙的案例。

我的看法是：如果时间充裕，建议学；如果时间紧张，先把中心扩展和 DP 吃透。Manacher 在面试中很少被要求手撕，但了解它的思想（利用已计算的回文半径来避免重复扩展）能让你对回文问题的理解再上一个台阶。

简单说，Manacher 把奇偶中心统一为每个字符加上分隔符，比如"aba"变成"#a#b#a#"，这样所有回文都变成奇数长度，然后维护当前最右边界和对应的中心，用对称性质初始化半径。代码量不小，容易记混淆。我当年是在刷题中期啃下它的，费了三天，但之后再看回文题就豁然开朗。

6.2 实际工程场景中会遇到这类问题吗？

说实话，日常业务开发里很少直接让你求“最长回文子串”。但回文检查、字符串反转、对称性判断在文本处理、日志分析、DNA 序列研究中都有应用。更关键的是，这道题训练的“中心枚举”和“区间 DP”思维，会迁移到很多看似无关的问题上，比如：

• 寻找最长有效括号子串（LeetCode 32）就可以用类似的中心扩展思想。
• 统计不同回文子序列（LeetCode 730）需要更复杂的 DP，但核心还是回文状态转移。
• 判断一个链表是否为回文链表（LeetCode 234）用的是快慢指针 + 反转后半段，也是对称性的变体。

所以，刷题的价值不在于背诵题解，而在于把一类结构想清楚。以后遇到新的对称性问题，你会自然而然地想到“从中间往外看”或“用区间状态记录”。

6.3 我的刷题习惯建议

最后聊聊我个人刷这道题时的习惯。我会在提交通过后做三件额外的事：

1. 把代码中的所有边界条件都注释一遍，确保每个条件都有存在理由。比如if not s、if n < 2、L <= 3这些，我会问自己“删掉会不会出错”。
2. 用不同的用例跑一遍，包括全相同字符、完全无回文、长度 1、长度 2。
3. 在自己的笔记本上手动画一遍 DP 表格，把"babad"的 dp 矩阵写出来。第一次画的时候你会发现，表格右上方大面积是 False，只有几个位置是 True，这个视觉效果比任何文字都加深记忆。

经验这东西，光看不练是留不住的。这道题代码量不大，很适合作为你复现“讲题笔记”的模板。我强烈建议你尝试自己先写一遍，遇到卡壳再回来看这篇，效果会好很多。