最长回文子串三种解法：中心扩展、动态规划与马拉车算法

1. 先把这道题彻底读透：最长回文子串到底在考什么

1.1 题目本质与解题目标

LeetCode Hot 100里的第5题“最长回文子串”，我刷了不止一遍，每次面试前都会重新过一下。这道题表面上是让你在一个字符串里找最长的回文子串，比如"babad"里答案是"bab"或"aba"，"cbbd"里答案是"bb"。本质上考的是三件事：你能不能快速识别回文的对称结构、能不能把重复的比较过程优化掉、以及你手里的算法工具箱里到底有几套方案。

很多初学者一上来就暴力枚举所有子串，再逐个判断是否回文，字符串一长直接超时。这道题真正的门槛不在“会不会判断回文”，而在“能不能用合理的复杂度把最长那个找出来”。面试官拿这道题出来，基本是想看你对字符串问题的敏感度，以及你能不能从 O(n³) 一步步优化到 O(n²) 甚至 O(n)。

适合看这篇内容的人很明确：准备算法面试的开发者、在Hot 100里刷题刷到这道题卡住的新手，以及想系统补一下回文串三种解法（中心扩展、动态规划、马拉车）的老手。我会把三种方案全部拆开讲，包含代码、复杂度、边界坑，以及我实际刷题和面试时踩过的真实教训。

1.2 暴力法为什么注定被淘汰

先看最直觉的暴力思路：枚举所有子串的起点i和终点j，然后写一个isPalindrome(s, i, j)去逐个字符比对。枚举子串本身是 O(n²)，每个子串判断回文最坏又是 O(n)，整体 O(n³)。n=1000时就是十亿次字符比较，在LeetCode的用例规模下基本必挂。

我在初学阶段真写过这种代码，当时还觉得思路挺清晰，直到提交后看到超时红色大字才意识到问题。暴力的核心浪费在于：判断s[i..j]是否回文时，完全没有复用s[i+1..j-1]的判断结果。而回文有一个天然的性质——一个子串如果是回文，去掉首尾后依然回文。这个性质就是所有优化方案的出发点。

所以后续的每一种解法，本质上都在做同一件事：想办法利用回文的对称性和子结构，把重复的比较结果缓存或跳过。理解了这一点，再看中心扩展、动态规划、马拉车就不会觉得它们是三个孤立算法，而是同一个问题的三种不同优化视角。

2. 中心扩展法：我最推荐的面试首选写法

2.1 核心思路与两种扩展形态

中心扩展法的想法非常朴素：回文串是关于中心对称的，那我只要枚举每一个可能的“中心点”，然后向左右两边同时扩展，直到两边字符不再相等，就能得到以该中心为对称轴的最长回文子串。

这里有一个关键细节：中心点有两种形态。奇数长度的回文，中心是某一个具体字符，比如"aba"的中心是'b'；偶数长度的回文，中心是两个字符之间的“空隙”，比如"abba"的中心在'b'和'b'之间。所以枚举中心的时候，必须同时考虑这两种情况，分别调用同一套扩展逻辑，再取较大值。

为什么这个方法值得作为首选？因为它空间复杂度是 O(1)，不需要额外开二维数组，实现逻辑也足够简单，面试现场不容易写崩。时间复杂度 O(n²)，对大多数面试场景完全够用。LeetCode原题的数据规模下，中心扩展法也能稳定通过，不像暴力法会超时。

我实际写题时的心得是：把“计算以某个中心开始的最长回文长度”抽成一个独立函数，接收左指针和右指针作为起始位置，内部用 while 循环扩展。这样主逻辑就非常干净，奇数偶数两种中心点调用两遍即可，也不容易漏边界条件。

2.2 完整代码实现与参数说明

class Solution: def longestPalindrome(self, s: str) -> str: if not s or len(s) < 1: return "" start = 0 max_len = 1 def expand_around_center(left: int, right: int) -> int: # 向左右两边扩展，返回扩展后的回文长度 while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 # 循环结束时 left 和 right 已经越界或指向不相等字符 return right - left - 1 for i in range(len(s)): # 奇数长度回文，中心是 s[i] len1 = expand_around_center(i, i) # 偶数长度回文，中心在 s[i] 和 s[i+1] 之间 len2 = expand_around_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]

这里有三个容易出错的位置需要重点说明。第一，expand_around_center返回的是right - left - 1，因为循环退出前最后一次left -= 1; right += 1已经把指针推到了不合法位置，真正的回文区间是[left+1, right-1]，长度就是right-left-1。第二，计算start时用i - (cur_len - 1) // 2，这里加不加cur_len - 1很关键，建议自己拿"cbbd"跑一遍体会偶数场景。第三，初始max_len设为 1，因为单字符本身一定回文，字符串非空时答案长度至少是 1。

我还建议在主函数开头先处理s为空的特殊情况，直接返回空字符串。虽然LeetCode的用例不一定有空串，但代码的健壮性是面试考核的一部分，细节分不能丢。

2.3 为什么中心扩展比动态规划更适合现场写

我自己在面试时基本首选中心扩展，原因很现实：动态规划虽然思路也清晰，但要维护二维数组dp[i][j]，当场写的时候很容易在遍历顺序上翻车；马拉车算法代码更短但原理绕，讲不清楚反而减分。中心扩展是一个“思路简单、代码好写、复杂度达标”的均衡解，面试官问复杂度也能对答如流。

对比一下两者的实际代码体积：中心扩展大概 20 行内搞定，动态规划要额外初始化二维数组并处理斜向依赖，马拉车则需要预处理字符串和计算p数组。从记忆负担来讲，中心扩展是最轻的。如果你面试时间紧张，我建议先把中心扩展练到闭眼能写、每一个细节都能解释清楚，再考虑进阶方案。

3. 动态规划：最严谨的递推思路

3.1 状态定义与状态转移方程

动态规划的解法和中心扩展在思路上完全不一样，它是从“子结构”入手的。定义dp[i][j]表示子串s[i..j]（包含两端）是否为回文。那么可以写出递推关系：

dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i+1][j-1])

这个方程怎么理解？如果s[i] != s[j]，那s[i..j]一定不是回文，因为首尾都不等。如果首尾相等，那s[i..j]是不是回文就取决于去掉首尾后的s[i+1..j-1]是不是回文。这里有个特例：当区间长度小于等于 3 时，只要首尾相等，中间只剩 0 个或 1 个字符，必定回文，所以不需要再看dp[i+1][j-1]。

这个“长度小于 3 直接为真”的细节，其实就是j - i < 3这一项存在的原因。很多人写动态规划时漏掉这个条件，导致数组访问越界或结果错误。边界情况单独用if处理也是一种方式，但把条件直接写进转移方程更优雅，也能少写分行代码。

3.2 遍历顺序是最大的坑

动态规划版本的代码我写了不止一次，每次栽跟头都栽在遍历顺序上。因为dp[i][j]依赖dp[i+1][j-1]，也就是说长区间的答案依赖更短的区间。如果按照i从 0 到 n、j从 i 到 n 的顺序去填表，你会发现计算dp[0][4]时，dp[1][3]可能还没算出来，结果全是错误的。

正确做法是按子串长度从小到大遍历。先算长度为 1 和 2 的所有子串，再算长度为 3 的，依次往上。对应代码就是外层循环枚举长度L，内层循环枚举起始位置i，终点j = i + L - 1。初始化时，dp[i][i] = True（单个字符），长度为 2 的子串直接判断s[i] == s[i+1]。

我在实际刷题中犯过一个很蠢的错误：先初始化dp[i][i] = True，也处理了长度 2 的情况，但外层长度循环从 1 开始而不是从 2 开始，导致重复计算和数组越界。后来养成了习惯——先列清楚长度为 1、2 的基例，再从长度 3 开始递推，逻辑就顺了。

3.3 完整代码与空间优化

class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start = 0 max_len = 1 # 长度为 1 的子串一定是回文 for i in range(n): dp[i][i] = True # 按长度从小到大遍历 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: # 长度 2 或 3 时，首尾相等即为回文 dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and L > max_len: start = i max_len = L return s[start:start + max_len]

动态规划的优点是思路严谨、状态定义清晰，面试时讲递推方程会显得你基础扎实。缺点是空间复杂度 O(n²)，当字符串长度上万时内存吃不消。不过 LeetCode 原题 n 最多 1000，完全没问题。

如果想要空间 O(n) 的降维版，可以用一维数组滚动更新，因为dp[i][j]只依赖dp[i+1][j-1]，本质上只依赖上一层的左下方位置。但注意压缩时遍历方向要按i从大到小，否则会覆盖掉还没用到的旧值。我个人建议面试时先写二维版本，简单直观不容易出错，等面试官追问空间优化再提一维版本。

4. 马拉车算法：线性复杂度的进阶武器

4.1 预处理技巧与对称性利用

马拉车算法的目标很明确：把时间复杂度压到 O(n)。它充分利用了回文的镜像对称性。具体做法是先对原字符串做预处理，在每个字符之间以及首尾都插入一个特殊分隔符，比如#。原字符串"abc"变成"#a#b#c#"，这样做的好处是统一了奇偶长度回文，所有回文在新串中都变成奇数长度，中心必然落在某个字符或#上。

然后定义一个数组p[i]，表示以新串第i个位置为中心能扩展出的回文半径（包含中心本身）。比如"#b#"中p[2] = 2。核心优化在于：维护当前所有回文中右边界最靠右的一个，记其中心为mid、右边界为right。当计算新的位置i时，先利用mid的对称性找到i的镜像位置i_mirror = 2 * mid - i。如果i < right，那p[i]至少可以取min(p[i_mirror], right - i)，因为i的回文至少能覆盖到right以内与镜像位置对称的部分。

直接看代码可能更清楚，我写过一个注释比较详细的版本。

4.2 马拉车标准实现

class Solution: def longestPalindrome(self, s: str) -> str: # 预处理，插入分隔符 t = '#' + '#'.join(s) + '#' n = len(t) p = [0] * n mid = 0 right = 0 max_radius = 0 max_center = 0 for i in range(n): if i < right: # 利用对称性初始化 p[i] i_mirror = 2 * mid - i p[i] = min(p[i_mirror], right - i) else: p[i] = 1 # 继续扩展 while i - p[i] >= 0 and i + p[i] < n and t[i - p[i]] == t[i + p[i]]: p[i] += 1 # 更新最右边界 if i + p[i] > right: mid = i right = i + p[i] if p[i] > max_radius: max_radius = p[i] max_center = i # 还原原始字符串中的起始位置 # 原串回文长度 = max_radius - 1 orig_len = max_radius - 1 start_orig = (max_center - max_radius + 1) // 2 return s[start_orig:start_orig + orig_len]

这里的“继续扩展”一段和中心扩展法的逻辑类似，但因为有了前面p[i]的初始值，很多位置的比较次数被大幅压缩，总体复杂度降到线性。关于还原部分：新串中中心为max_center、半径为max_radius的回文对应原串起点是(max_center - max_radius + 1) // 2，原串回文长度是max_radius - 1。这个换算我第一次推的时候还花了点时间，直接记结论再配合两个例子验证即可。

马拉车虽然代码不长，但在面试中属于加分项。我一般在面试官追问“能不能做到 O(n)”时才提它。值得注意的是，马拉车对理解对称性和边界条件的要求较高，如果你在现场不能把p[i]的初始值为什么是min(p[i_mirror], right - i)讲清楚，建议不要主动往这个方向引，以免被追问到露怯。

4.3 三种解法怎么选

我给你的选型建议是这样的：如果面试时间紧、压力大，直接上中心扩展，稳扎稳打；如果面试官明确要求用动态规划展示递推思维，再写二维 DP；如果 String 类题目你已经刷得很熟，马拉车作为储备能让你在“复杂度还能不能再优化”的问题上游刃有余。

我在实际工作中写业务代码几乎不会遇到需要马拉车的场景，但刷题和面试是完全另一套评价体系。这道题三种解法全掌握，相当于把字符串处理里最经典的对称性问题彻底吃透了，后面遇到“最长回文子序列”“回文对”等变种题，也能有个清晰的类比基础。

5. 边界测试与高频错误排查实录

5.1 必测的边界用例清单

无论用哪种解法，提交前我建议你把这组用例在本地跑一遍，能覆盖绝大多数边界场景：

我自己刷题时习惯把这些用例写成函数调用的形式批量测试，而不是手动一个一个看。写一个简单的断言列表，跑一遍省心很多。尤其是"aaaa"这种用例，能暴露中心扩展里start计算错误的问题。

5.2 三个高频错误与修复方法

第一个高频错误是中心扩展法的start位置算错。表现为输入"cbbd"时输出"b"而不是"bb"。问题基本都在start = i - (cur_len - 1) // 2这条公式上。我建议复盘时用i=1, cur_len=2代入（字符串"cbbd"中，中心在b和b之间），你会发现如果不减 1，算出的起点会偏右一位，切出来的子串就不是完整回文。

第二个高频错误是动态规划遍历顺序写错。很多人按i从前往后、j从i往后去填表，结果答案完全不对。只要记住一句口诀：子串题意依赖短串，长度从短到长遍历。外层循环一定是长度，内层才是起点，这个顺序反了，整个表都是脏数据。

第三个高频错误是马拉车里right - i与p[i_mirror]取最小值时理解不清。有些人直接写p[i] = p[i_mirror]，在镜像位置的回文超出当前右边界时就会越界或结果偏大。正确写法必须带上min约束，因为超出right的部分还没被验证过，不能直接镜像推断。

5.3 面试中常见的追问方向

面试官大概率会追问这三类问题。第一是“为什么中心扩展时间复杂度是 O(n²)？”回答思路：枚举中心 O(n)，每次扩展最坏 O(n)，两者相乘。强调最坏情况是全部字符相同的时候，每次扩展都要走到边界。第二是“动态规划还能优化空间吗？”提一维滚动数组，但注意说明遍历方向要调整。第三是“马拉车为什么能做到 O(n)？”解释right边界只增不减，每个位置最多被扩展成功一次，失败则立即停止，所以总扩展次数是线性的。

这些问题都不难，但前提是你真的理解了你写的每一行代码。我在面试别人的时候经常发现，能把中心扩展讲清楚的人很多，但能把 DP 的遍历顺序和马拉车的min分支讲明白的人少一半。这差距就是准备的深度问题。

6. 一点刷题实战体会

这道题我刷过好几轮，每次重刷都有新的理解。第一次学动态规划，硬背代码，过两天就忘了；第二次认真推导状态转移方程，总算明白了遍历顺序的来源；第三次系统学习马拉车，才真正理解“对称性复用”的精妙。所以如果你第一次看完没完全吃透，非常正常，这不是一道看一遍就能会的题。

我的建议是：先用中心扩展法把题过了，然后隔一天再用动态规划重新写一遍，不参考任何资料，看看能不能自己推导出遍历顺序。最后再挑一个周末啃一下马拉车，把p[i] = min(p[i_mirror], right - i)这个关键算式亲手在纸上验证两个例子。三步走完，这道题才算真正转化成你自己的能力。

另外提醒一句：LeetCode Hot 100 里回文相关的题不止这一道，“回文子串”“最长回文子序列”都和它有关联。把第 5 题吃透，后面遇到这些变种会轻松很多。