最长回文子串：从暴力到Manacher的四种解法与面试攻略

聊到算法面试必刷清单，最长回文子串（LeetCode 5）几乎是一定会出现的名字。这道题我当候选人时被面过不下十次，后来自己做算法面试官，也经常拿它当热身题。它之所以被各个大厂反复使用，不是因为解法有多难背，而是因为一道题就能考察到两种不同的思维路径：一种是区间动态规划，一种是线性复杂度的马拉车算法，中间还夹着一个"大家都能想到但细节极多"的中心扩展。这篇文章我会把暴力、动态规划、中心扩展、Manacher 四种思路完整拆开，附带可以直接背下来的代码，以及面试时怎么一步步和面试官沟通，把复杂度从 O(n³) 一路聊到 O(n)。

1. 一道题刷出四层境界：最长回文子串到底在考什么

1.1 题目定义与基础概念

题目描述很简单：给定一个字符串s，找到s中最长的回文子串。回文串就是正着读和反着读一样的字符串，比如"aba"、"racecar"、"abba"。注意是子串，也就是必须连续的一段，不能像子序列那样跳着取。所以"babad"的最长回文子串是"bab"或者"aba"（两者长度都是 3，题目说返回任意一个都可以），"cbbd"的最长回文子串就是"bb"。

这道题在 LeetCode 上是中等难度，但实际面试里的考察深度远超"中等"这两个字。原因在于它解法梯度非常清晰：先是一个三层循环的暴力解让大家确认题目理解，然后可以升级到动态规划或中心扩展的 O(n²) 解法，最后还能延伸到 O(n) 的 Manacher 算法。每一层都需要不同的思维工具，从枚举、递推到对称性优化，恰好覆盖了算法面试最常问的几类能力。

1.2 四种解法对应面试官的四种期待

我面过不少候选人，观察到一个规律：大部分人在 10 分钟内能写出中心扩展法，这是合格线；能写出动态规划并解释清楚填表顺序的，说明区间 DP 基本功扎实；能主动提出 Manacher 或者在被追问后把线性算法讲明白的，基本就是加分项了。很少有人会先写暴力解，但真有人写的话，我反而会好感度上升，因为他展现了"先确认问题，再逐步优化"的工程习惯。

你需要知道的是：面试官不是期待你一上来就甩出 Manacher，而是看你能不能沿着"暴力→优化→再优化"的路径走下来。接下来我把每层境界都拆开讲，包括代码和推导过程，这样不管面试官问到哪一层，你都有完整的答案。

1.3 为什么说这道题是最典型的面试题

典型之处在于它的边界条件特别容易出错。空串返回什么？单个字符算不算回文？字符串长度是偶数还是奇数？这些细节会直接影响代码里的循环范围和返回值。另一层典型体现在复杂度选择的权衡：O(n²) 时间 O(1) 空间的中心扩展在绝大多数场景下已经够用，但一旦面试官追问"如果字符串长度是百万级别呢"，你就得有 O(n) 的备用方案。

我自己的经验是：刷这道题时不要只背代码，要把四种解法当成四个独立的小项目来理解。理解了每种解法背后的"为什么"，面试时你才能做到游刃有余。

下面给出四种解法的复杂度对比，方便你有个整体印象：

2. 暴力解不是白写的：枚举所有子串时能看出哪些门道

2.1 最直接的思路：枚举所有子串再逐个判断

暴力解法分两步：第一步枚举所有子串，第二步对每个子串判断它是否回文。枚举子串需要确定起点和终点，双层循环是 O(n²) 个子串；每个子串判断回文用双指针从两端向中间扫描，又是 O(n)。三层嵌套下来就是 O(n³)。代码大概长这样：

def longestPalindrome_bruteforce(s: str) -> str: n = len(s) if n < 2: return s max_len = 1 start = 0 # 枚举所有起点和终点 for i in range(n): for j in range(i, n): # 判断 s[i:j+1] 是否是回文 l, r = i, j ok = True while l < r: if s[l] != s[r]: ok = False break l += 1 r -= 1 if ok and j - i + 1 > max_len: max_len = j - i + 1 start = i return s[start:start + max_len]

这段代码在面试里建议不要真的从头写到尾，除非面试官明确让你给出最朴素版本。你只需要口头描述一下"我可以枚举所有子串，然后逐个用双指针验证"，然后紧接着指出复杂度是 O(n³)，面试官通常就会让你继续优化。能主动分析复杂度，比闷头把代码写完更重要。

2.2 剪枝思路：把枚举顺序倒过来

暴力解法有一个很容易想到的优化：既然要找最长的，那就从最长的子串开始枚举，找到第一个回文就直接返回。这种"从长到短 + 提前终止"的策略能把平均运行时间缩短很多，虽然最坏复杂度还是 O(n³)，但实际跑起来快不少。

还有一种优化是在判断回文之前先做一次长度剪枝：如果当前枚举的子串长度小于已经找到的最长回文长度，直接跳过，没必要再判断。这个剪枝在随机字符串上效果尤其明显。不过我必须坦白说，这类剪枝属于工程上的微调，面试中谈一谈可以体现「你考虑过常数优化」，但不要指望它能改变算法等级。

2.3 暴力的真正价值：当测试基准和兜底方案

很多人觉得暴力解一无是处，我不同意。暴力解的代码逻辑最简单，几乎不可能因为边界条件写错，所以它天然适合做"基准实现"。我在自己刷题时有个习惯：先用暴力解跑通，再用中心扩展或者 Manacher 去验证随机输入的结果是否一致。你会发现高级算法在边界处理上一旦写错，跑几个大用例很难看出来，但和暴力结果一对比，问题立刻暴露。

面试里如果你时间充裕，也可以采取类似策略：先和面试官说明暴力思路，然后在实现更优解法时用简单例子手动推演验证。这种「先能跑通，再谈优化」的工程思维，其实比算法本身更容易打动面试官。

3. 动态规划版本：回文子串的"区间递推"

3.1 dp 数组的定义与状态转移推导

动态规划的核心是把大问题拆成小问题。对于一个子串s[i..j]（闭区间），它是否为回文串，取决于两个条件：s[i]是否等于s[j]，以及去掉两端后的s[i+1..j-1]是否为回文串。用数学表达就是：

• dp[i][j]表示s[i..j]是否为回文字符串（布尔值）
• 当s[i] == s[j]时，dp[i][j] = dp[i+1][j-1]
• 当s[i] != s[j]时，dp[i][j] = false

这里需要单独处理基线条件：长度为 1 的子串一定是回文，所以dp[i][i] = true；长度为 2 的子串只要s[i] == s[i+1]就是回文，所以dp[i][i+1] = (s[i] == s[i+1])。这两个条件可以合并到状态转移里，写成：

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

这里的j - i < 3意思是：长度为 1 或 2 的子串（因为闭区间长度是 j-i+1），只要两端字符相等就直接是回文，不需要看中间部分。用这个写法可以少写两个显式的初始化分支，代码更简洁。

3.2 填表顺序为什么必须先短后长

这部分是动态规划最容易出错的地方。dp[i][j]依赖的是dp[i+1][j-1]，也就是长度更短的子串。如果按起点 i 从前往后遍历、终点 j 也从前往后遍历，那么计算dp[i][j]时，dp[i+1][j-1]可能还没被计算出来。

正确做法是先枚举子串长度，再枚举起点。长度从 2 开始逐步增加到 n，这样才能保证计算长区间时，所有短区间的结果都已经就绪。曲线救国的方式也可以：让 i 从大到小遍历、j 从小到大遍历，同样能保证dp[i+1][j-1]先于dp[i][j]被计算。不过最直观、最不容易出错的还是按长度枚举。

3.3 完整代码与空间优化方向

下面用 Python 实现一遍，尤其注意start和max_len的更新逻辑：

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 # 长度为 1 的子串一定是回文 for i in range(n): dp[i][i] = True # 按子串长度从小到大枚举 for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] != s[j]: dp[i][j] = False else: if length == 2: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and length > max_len: max_len = length start = i return s[start:start + max_len]

二维数组的空间复杂度是 O(n²)。如果面试官追问能不能压缩空间，可以提一句：其实只需要保留上一轮长度的状态，用一个一维数组滚动更新就能把空间降到 O(n)。具体做法是从右往左更新一维数组，避免旧值被覆盖。不过说实话，在面试中写二维版本是更安全的选择，空间优化口头说明即可，真要写的话反而容易因为顺序问题翻车。

面试中谈到动态规划，还有一件事容易被追问：为什么dp[i][j]的回文长度等于j-i+1？因为dp数组存的就是布尔状态，最长回文长度只跟i、j的差值有关。这个想清楚，后面的中心扩展法其实本质上就是另一种省空间的 DP 实现。

4. 中心扩展法：面试官眼里最稳的 O(n²) 解法

4.1 回文的对称性才是核心洞察

动态规划虽然思路清晰，但二维数组的空间消耗并不理想。中心扩展法的出发点完全不同：回文串天然是"轴对称"的，所以每个回文串都有一个对称中心，从这个中心向两侧扩展，只要两侧字符相同，就能继续构成回文。

这个洞察带来的算法非常直观：遍历字符串中的每一个位置，把它当作回文中心，然后向左右两侧扩展，记录能扩展到的最大长度。关键点在于，回文的中心有两种情况：奇数长度回文的中心是一个字符（比如"aba"的中心是'b'），偶数长度回文的中心是字符之间的空隙（比如"abba"的中心在中间两个'b'之间）。所以每个位置不仅要当作单独字符中心试一次，还要当作"空隙中心"试一次。

4.2 为什么是 2n-1 个中心

一个长度为 n 的字符串，有 n 个字符位置可以作为奇数回文的中心，有 n-1 个字符之间的空隙可以作为偶数回文的中心，合计 2n-1 个中心。对每个中心，向两边扩展的代价最坏是 O(n)，所以总时间复杂度是 O(2n-1) × O(n) = O(n²)。空间上只需要几个变量，是 O(1)。

我在面试中经常让候选人写这个解法，因为它的代码量很短，但对"中心"这个概念的理解要求很高。如果你能清晰地说出 2n-1 的来源，并且分别处理奇偶两种情况，那基本就过关了。

4.3 完整代码与边界处理

中心扩展的代码我建议直接背下来，它足够短，而且不容易出错：

def longestPalindrome_expand(s: str) -> str: if not s or len(s) < 1: return "" start = 0 end = 0 for i in range(len(s)): # 奇数长度回文，中心为 i len1 = expand(s, i, i) # 偶数长度回文，中心为 i 和 i+1 之间的空隙 len2 = expand(s, i, i + 1) cur_len = max(len1, len2) if cur_len > end - start + 1: start = i - (cur_len - 1) // 2 end = i + cur_len // 2 return s[start:end + 1] def expand(s: str, left: int, right: int) -> int: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 # 循环结束后，left 和 right 已经越过了回文边界 # 回文长度为 right - left - 1 return right - left - 1

这里容易踩的小坑是坐标换算。当算出回文长度cur_len后，新的起点是i - (cur_len - 1) // 2，终点是i + cur_len // 2。这个式子对奇偶两种情况都成立，你可以拿"cbbd"里的"bb"手推一遍：中心是 i=1 和 i=2 之间，expand返回 2，start = 1 - 0 = 1，end = 1 + 1 = 2，结果正好是s[1:3] = "bb"。

4.4 DP 和中心扩展怎么选

时间复杂度上两者都是 O(n²)，但中心扩展的空间优势太明显了：DP 需要 O(n²) 的布尔矩阵，中心扩展只需要 O(1)。所以在面试场景下，我的建议是优先写中心扩展，它代码更短、空间更少、逻辑也更直观。动态规划的价值在于体现你掌握区间 DP 这种更通用的工具，而且有些题目（比如回文子序列）必须依靠 DP 思路。所以两道题都该会，但针对这道题本身，中心扩展是对大多数候选人来说性价比最高的答案。

5. Manacher 算法：从 O(n²) 到 O(n) 的关键三步

5.1 预处理：用 # 和哨兵统一奇偶回文

Manacher 算法是这一题的正统 O(n) 解法，它的优化思路是"利用已经算出来的回文信息，避免重复扩展"。新手第一次看 Manacher 基本都会被绕晕，我按三个步骤拆开讲，每一步都有对应的物理意义。

第一步，预处理字符串。把原始字符串的每个字符之间插入一个特殊字符#，并且在开头和结尾再加两个哨兵字符（比如^和$）。例如"abba"变成"^#a#b#b#a#$"。#的作用是把偶数长度回文的"空隙中心"变成显式的字符中心，这样一来，不管原来的回文是奇数长度还是偶数长度，在新字符串里都统一以某个字符为中心。哨兵的作用是让扩展循环到达边界时必然失配，从而不需要做越界判断。

第二步，定义回文半径数组p[i]。它的语义是：以新字符串的第 i 个字符为中心，能向两侧扩展的最大步数。也就是说，t[i-p[i] .. i+p[i]]这一段一定是回文。特别地，原始字符串中的最长回文子串长度，就恰好等于max(p)。

5.2 p 数组的镜像复用逻辑

第三步是整个算法的核心：维护两个变量center和right，分别表示当前已知最右回文串的中心和右边界。当你需要计算某个位置 i 的p[i]时，如果 i 在right的左侧，说明 i 落在一个已知回文范围内。利用回文的对称性，i 关于center的镜像位置是mirror = 2 * center - i，而镜像位置的回文半径p[mirror]大概率已经被算过了。

这时候分两种情况：如果镜像的回文范围完全落在已知回文串内，那么p[i]至少等于p[mirror]；如果镜像的回文范围超出了已知回文串的左边界，那么p[i]至少等于right - i，再往外就要暴力扩展了。综合起来就是：

if i < right: p[i] = min(p[mirror], right - i)

这个min是 Manacher 的精髓：它保证了你不会去扩展一个已经被确认过的范围，只在必要时才暴力扩展。

5.3 均摊 O(n) 的原因

为什么总复杂度是 O(n)？关键在于right这个右边界是单调递增的。每次暴力扩展成功一次，right就会变大一点，而right最多只能到数组末尾。换句话说，虽然每个位置都可能触发扩展，但整体扩展成功的次数被right的上限限制住了。暴力扩展的总次数是 O(n)，再加上每个位置 O(1) 地计算p[i]初始值，总复杂度就是 O(n)。这个均摊分析在面试时值得详细讲给面试官听，能体现出你真的理解而不是背模板。

5.4 完整代码与容易写错的三处细节

我给出一个可以直接跑的 Python 实现：

def longestPalindrome_manacher(s: str) -> str: if not s: return "" # 预处理：插入 # 并加哨兵 t = '^#' + '#'.join(s) + '#$' n = len(t) p = [0] * n center = 0 right = 0 max_len = 0 max_center = 0 # 跳过最左和最右的哨兵 for i in range(1, n - 1): if i < right: mirror = 2 * center - i p[i] = min(p[mirror], right - i) # 暴力扩展：利用哨兵避免了越界判断 while t[i + p[i] + 1] == t[i - p[i] - 1]: p[i] += 1 # 更新 center 和 right if i + p[i] > right: center = i right = i + p[i] if p[i] > max_len: max_len = p[i] max_center = i # 根据中心位置和半径还原原始子串的起点 start = (max_center - max_len) // 2 return s[start:start + max_len]

这里有三处经常写错的地方，我特别标一下：

• 先更新center和right，再更新答案。因为right可能因为当前 i 的扩展而变大，如果不先更新，后面的位置就会用到一个过期的右边界。
• p[i]的初始值不是固定为 0，而是min(p[mirror], right - i)，这是算法能够跳过重复比较的关键。
• 还原起点时是start = (max_center - max_len) // 2，不是max_center - max_len，因为我们要把新字符串的下标映射回原始字符串的下标。

5.5 一个额外收获：回文子串计数

Manacher 的p[i]还有一个作用：直接数出所有回文子串的数量。以每个中心为轴，半径从 1 到p[i]都可以构成一个回文，所以把所有的p[i]加起来，就是整个字符串中回文子串的总数。LeetCode 647 就是这道题。在面试中如果你能主动提到这一点，面试官基本可以确认你真正掌握了 Manacher 而不是背了个模板。

6. 面试实战：从确认题意到被追问的完整话术

6.1 动笔之前先和面试官对清楚这几件事

我在面试中观察到，能在写代码前主动沟通边界的候选人往往比直接上手写代码的更有好感。针对这道题，动笔前至少要确认四件事：

第一，输入字符串可能为空吗？如果为空应该返回空串还是 null？第二，单个字符算回文吗？按照通常定义单个字符天然是回文，但最好和面试官确认。第三，输入字符串包含哪些字符？如果只有小写字母，Manacher 的哨兵选^和$就很安全；如果有任意 ASCII 或 Unicode，需要考虑哨兵冲突或者改用边界判断。第四，如果存在多个同样长度的最长回文子串，返回任意一个即可吗？LeetCode 原题说任意一个，但还是确认一下更稳妥。

这些问题不是走过场。有一次面试中，候选人对空串和单字符做了显式处理，后来代码在边界上几乎没有返工，让我印象很深。

6.2 测试用例与边界清单

代码写完之后，不要急着交差，主动跑几个用例是加分项。我习惯的验证用例是：

• 空串""：返回""
• 单字符"a"：返回"a"
• 偶数长度回文"cbbd"：返回"bb"
• 奇数长度回文"babad"：返回"bab"或"aba"
• 全相同字符"aaaa"：返回"aaaa"
• 陷阱用例"abacdfgdcaba"：这里"abacdfgdcaba"本身不是回文，但"aba"和"aba"是，容易让人误以为整个串是回文，正好检验枚举逻辑
• 两个互相重叠的中间有个"bananas"："anana"是最长回文

手动推演两三个用例就够了，重点是要把 push 到有回文中心但边界不对的例子，比如"aaabaaaa"这种，能暴露出你在更新start和end时的坐标错误。

6.3 我踩过的坑和候选人常犯的错误

第一坑：中心扩展法里，只处理了expand(s, i, i)而漏掉expand(s, i, i+1)。这个词面看很简单，但在紧张的面试环境中很容易漏，漏掉之后所有偶数长度回文都会被跳过。第二坑：动态规划填表顺序错误。这个一错那就是整体逻辑全崩，因为dp[i+1][j-1]还没算出来。第三坑：Manacher 里p[i]初始值设成 0，然后无条件扩展，这样虽然结果不错但复杂度退回 O(n²)，完全失去意义。第四坑：坐标换算时把闭区间和半开区间搞混，substring(start, end)和substring(start, end + 1)差一个字符，结果就是最长回文总是少了头或尾。

我自己的教训是：所有的坐标边界问题，都要用长度为奇数和偶数的两个小例子去手动验证一遍。"aba"（奇数中心）和"abba"（偶数中心）是所有这类题目逃不掉的黄金测试对。手动推演一次，比事后 debug 快得多。

6.4 如果只剩 15 分钟，就写中心扩展

最后说点实战策略。面试中你的时间分配大约是：5 分钟聊思路和边界，10 到 15 分钟写代码，最后 5 分钟测试验证。如果时间不够，直接写中心扩展法，它的代码量最小，逻辑最容易自洽，出 bug 的概率也最低。如果时间充裕且面试官明确对更优复杂度感兴趣，可以上 Manacher，但前提是你真的理解了right单调性的证明，否则面试官一追问"为什么是 O(n)"就会露馅。

顺着这个话题多说一句：算法面试其实不只是考你会不会这道题，更多是考你在有限时间内能不能给出一个"正确、可解释、可验证"的完整方案。最长回文子串恰好把所有经典要素都凑齐了，所以把它刷透，性价比真的很高。我至今写这道题时，还是会先从中心扩展开始跑通，再考虑要不要换 Manacher，这个习惯帮我在多次面试里避免了低级失误，也希望对你有效。