最长回文子串算法详解：从中心扩展到动态规划与Manacher

1. 这道题为什么能进 TOP 面试题先看懂考官的出题意图1.1 表面考字符串实际考的是算法思维的进化路径最长回文子串LeetCode 第 5 题属于经典的不能再经典的动态规划/字符串题目。但面试官真的只是想考察你会不会判断回文吗不是的这道题的巧妙之处在于它的解法梯度非常完整从暴力枚举到中心扩展再到动态规划最后到 Manacher 算法每一层解法对应着不同的能力层次。你可以把这道题理解为一把尺子面试官用它可以量出候选人的算法功底在哪个位置。我帮组里招人的时候经常出这道题因为对标三年工作经验的 Java 后端候选人能写出中心扩展已经及格能写动态规划说明有竞赛基础或系统刷过题能讲清楚 Manacher 并且手写无误的我遇到的概率大约只有 5%。所以你看这题进 TOP 面试题不是因为它难而是因为它能稳定地筛出不同水平的人。另外从语言层面来说用 Java 实现这道题也有很多细节值得考比如substring()的边界处理、charAt()的频繁调用、StringBuilder做字符预处理时的性能表现。这些在实际业务代码里写不写得对面试官通过一道题就能看个大概。下面我把这道题的完整解题路径拆开从最朴素的暴力开始一步步走到线性复杂度的马拉车。1.2 一个最容易忽略的前提回文子串和回文子序列不是一回事在开始写代码之前有一个概念性的前提必须先搞清楚这道题求的是子串不是子序列。子串要求连续比如ababc中aba是合法的回文子串但aabaa不是因为原字符串里根本没有连续的aabaa。子序列则允许跳过字符那是另一道题LeetCode 516解法完全不同。很多人面试翻车就翻在这里——面试官问的是最长回文子串他上来就写了子序列的解法写完了还觉得挺对。所以第一步审题审清楚连续这两个字是整道题的第一性原则。提示如果题目要求返回的是最长回文子串的长度代码逻辑基本一致但在截取返回结果的环节略有差异。面试时建议主动和面试官确认返回值是字符串本身还是长度避免白写。2. 暴力枚举不是丢脸解法先跑通正确性再谈效率2.1 最直觉的思路列出所有子串逐个检查暴力解法的思路非常直白既然是找最长的回文子串那我枚举出所有可能的子串逐个判断是不是回文记录最长的那个就行。判断回文的逻辑大家初中就学过从两端往中间走两两对比字符遇到不相等就不是回文。public String longestPalindrome(String s) { if (s null || s.length() 2) { return s; } int n s.length(); int maxLen 1; int start 0; for (int i 0; i n; i) { for (int j i; j n; j) { if (isPalindrome(s, i, j) (j - i 1 maxLen)) { maxLen j - i 1; start i; } } } return s.substring(start, start maxLen); } private boolean isPalindrome(String s, int left, int right) { while (left right) { if (s.charAt(left) ! s.charAt(right)) { return false; } left; right--; } return true; }这段代码的亮点在于边界处理i j保证了子串有效s.substring(start, start maxLen)用的是起始位置 长度的写法避免了end索引越界的常见错误。我见过很多候选人写substring(start, end)结果 end 算错一位整个结果就偏了。2.2 复杂度推导为什么暴力解是 O(n^3)三重循环加起来就是 O(n^3)外层枚举起点 O(n)内层枚举终点 O(n)每次判断回文又要从两端往中间扫描 O(n)。所以总的时间复杂度是 O(n^3)空间复杂度是 O(1)只有两个临时变量。n 稍微大一点就完蛋。比如字符串长度是 1000最坏情况下要执行 10 亿次字符比较LeetCode 上 1000 级别的测试用例直接超时。所以暴力解只能作为一种确认我理解了题意的兜底方案真正提交肯定不行。2.3 但是如果一上来就写暴力解面试官会怎么想我的建议是面试中完全可以说出暴力思路但说完之后要立刻跟一句不过这个复杂度太高了n 到 1000 就扛不住我还可以用中心扩展优化到 O(n^2)。主动暴露暴力解的局限性比等面试官指出局限要好得多。这说明你有完整的复杂度意识知道自己的解法在什么量级会失效。我见过一些候选人一上来就闷头写 Manacher写完了但是讲不清楚为什么是对的。这种人反而让我更警惕——背模板的痕迹太重了。面试要的是可控的思考过程不是炫技。3. 中心扩展法面试现场最推荐的标准答案3.1 利用回文的对称性把枚举对象从子串换成中心暴力解低效的原因在于它枚举的是子串然后去验证对称性。但回文的一个天然属性是——它有一个对称中心从中心向两边扩展只要左右字符相等就还是回文。打个比方回文像一颗洋葱从中心开始一层一层往外拨。racecar的中心是e左边c、右边c相等再往外a、a相等再往外r、r相等。如果我枚举中心每次从中心往两边扩散找到该中心对应的最大回文半径那么所有回文子串都会被覆盖到而且每个中心只需要 O(n) 的扩展操作。那么一共有多少个中心关键点来了每个字符本身是一个中心奇数长度的回文每两个相邻字符中间也是一个中心偶数长度的回文。比如abba这个回文它的对称中心在b和b之间的缝隙里光枚举字符中心是覆盖不到的。所以中心总数是n (n - 1) 2n - 1个。3.2 统一奇偶把所有中心都视为缝隙两侧有了 2n-1 个中心剩下的事情就简单了。我写一个辅助函数expandAroundCenter(s, left, right)从给定的左右指针出发向两边扩展只要对称就继续最后返回扩展出的回文长度。对每个中心分别调用两次expandAroundCenter(s, i, i)字符 i 本身作为中心覆盖奇数长度回文expandAroundCenter(s, i, i1)i 和 i1 的中间作为中心覆盖偶数长度回文public String longestPalindrome(String s) { if (s null || s.length() 2) { return s; } int start 0, maxLen 1; int n s.length(); for (int i 0; i n; i) { int len1 expandAroundCenter(s, i, i); int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substring(start, start maxLen); } private int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }3.3 这个解法为什么是最值得优先掌握的中心扩展法的时间复杂度是 O(n^2)因为外层枚举了 2n-1 个中心每个中心最多向外扩展 n 次空间复杂度 O(1)非常省内存。它比暴力解好了两个数量级而且思路足够直观代码量也很短在面试的 30-40 分钟时间窗口内写出并讲清楚这段代码完全可行。相比之下动态规划虽然时间复杂度同样是 O(n^2)但空间要开到 O(n^2)而且状态转移处容易写错遍历顺序下一节细讲Manacher 虽然能优化到 O(n)但理解门槛高代码也不短。从面试性价比的角度看中心扩展是投入产出比最高的方案。3.4 中心扩展法最容易被轻视的两个细节第一个细节是start i - (len - 1) / 2这行。为什么不是i - len / 2因为对于奇数长度的回文中心位置i正好是中间那个字符对于len 3的回文i - 1是起点对于len 5i - 2是起点也就是(5-1)/2 2。而偶数长度回文由于中心在 i 和 i1 之间起点是i - len/2 1。这两种情况用(len - 1) / 2整数除法统一处理刚刚好。第二个细节是辅助函数的返回值为什么是right - left - 1。因为 while 循环退出时left和right多向外走了一步真实的回文区间是[left1, right-1]长度等于(right - 1) - (left 1) 1 right - left - 1。这是扩展类题目的通用套路不只是回文很多从中心向两边的问题都用这个公式。4. 动态规划解法状态转移是重点遍历顺序是深坑4.1 状态定义与转移方程用子问题的答案拼出原问题中心扩展法的本质是贪心地从里往外推而动态规划的思路正好反过来它是从短到长地递推。定义一个二维布尔数组dp[i][j]表示s[i..j]这一段子串是否为回文。那么状态转移的直觉是s[i..j]是回文当且仅当s[i] s[j]且s[i1..j-1]也是回文。就像剥洋葱时最外层一样剥掉之后里面还得是对称的结构这个子串才是完整的回文。转移方程写出来就是dp[i][j] (s[i] s[j]) (j - i 2 || dp[i1][j-1])这里的j - i 2是一个重要的边界处理当子串长度小于等于 3 时只要两端字符相等它必然是回文不需要依赖更短的子问题结果。比如aa长度 2两端相等中间没有内容当然是回文aba长度 3两端相等中间是单个字符也当然是回文。4.2 初始化与完整代码所有dp[i][i]初始化为true因为单个字符本身就是回文。然后从长度为 2 的子串开始逐渐递推到更长。public String longestPalindrome(String s) { if (s null || s.length() 2) { return s; } int n s.length(); boolean[][] dp new boolean[n][n]; int start 0, maxLen 1; for (int i 0; i n; i) { dp[i][i] true; } for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s.charAt(i) ! s.charAt(j)) { dp[i][j] false; } else { dp[i][j] (len 2) || dp[i 1][j - 1]; } if (dp[i][j] len maxLen) { maxLen len; start i; } } } return s.substring(start, start maxLen); }4.3 遍历顺序是这道题最大的暗坑必须按长度从小到大动态规划的遍历顺序非常容易写错。很多人下意识地用双重循环for i和for j外层 i 从 0 开始内层 j 从 i 开始逐个遍历。这样会出事dp[i][j]依赖dp[i1][j-1]也就是左下角的格子如果用 i 从小到大 的顺序遍历算dp[0][4]时依赖的dp[1][3]还没算出来拿到的就是默认值false答案就错了。所以正确的做法是按子串长度len从短到长遍历保证当我计算长度len的子串时所有长度小于len的子串状态都已经准备好了。这就好比盖楼必须从地基一层一层往上盖不能先盖三楼再盖二楼。如果你在实际推演中还是容易晕我建议用一个 5x5 的表格手动填一遍babad的例子。先填对角线dp[0][0]到dp[4][4]再填长度 2 的所有子串再填长度 3 的你会发现每一个格子依赖的dp[i1][j-1]都在上一轮循环里已经填好了逻辑就通了。4.4 空间优化从二维数组压到一维甚至零额外空间的思路二维dp的空间复杂度是 O(n^2)n 到 5000 就差不多要 25MB 内存了不太优雅。可以优化成滚动数组因为第len层只依赖第len-2层的结果用一个一维数组dp[j]代表当前长度下以 j 为结尾的子串是否是回文然后倒序更新可以压到 O(n) 空间。不过说实话这个优化在面试中属于加分项写不写不是关键关键是你能讲清楚为什么能这样压。甚至可以进一步做 O(1) 空间的动态规划——遍历所有中心不断向外扩张更新最长值这不就是中心扩展法吗所以你会发现一个有意思的结论中心扩展法本质上就是动态规划的 O(1) 空间版本 按中心枚举的遍历顺序。理解了这层关系两种解法就融会贯通了。5. Manacher 算法线性复杂度的进阶武器理解了就是碾压局5.1 预处理插入分隔符把奇偶情况统一成一个模板Manacher 算法的第一个核心技巧是预处理在原始字符串的每个字符之间以及首尾都插入一个特殊字符#。比如aba变成#a#b#a#abba变成#a#b#b#a#。这样做的好处是原字符串奇数长度和偶数长度的回文统一成了新字符串里奇数长度的回文且中心一定是某个字符或某个#不再需要区分奇偶两种情况。同时这个#是可以随意选的一个不会出现在原字符串中的字符比如#或者^、$这类边界哨兵只要保证它和原字符不冲突就行。处理后原来的最长回文长度就是新串的最大回文半径减 1最后从预处理串还原时再除以 2 就能拿到原串中的起始下标。5.2 回文半径数组与镜像复用避免重复扩展的杀手锏预处理之后定义一个数组p[i]表示以i为中心的最长回文半径含中心本身。如果p[i] k意味着t[i-k1 .. ik-1]是回文。Manacher 的核心优化思路是利用已有回文的对称性减少不必要的中心扩展。维护两个变量center是当前已知的最靠右回文的中心right是它的右边界。当我处理某个位置i时如果i right说明i落在已知回文区间内那么i关于center的镜像位置mirror 2 * center - i的回文半径已经算过了我可以直接把p[i]的初始值设为Math.min(right - i, p[mirror])。这里用right - i是因为不能超出已知回文右边界如果镜像位置的回文长度没超出左边界可以直接复用p[mirror]如果超出了就只能先取right - i剩下的部分再暴力扩展。这个能复用就复用的策略是 Manacher 能够做到 O(n) 的关键。5.3 完整 Java 实现与逐步推演public String longestPalindrome(String s) { if (s null || s.length() 2) { return s; } StringBuilder sb new StringBuilder(#); for (char c : s.toCharArray()) { sb.append(c).append(#); } String t sb.toString(); int n t.length(); int[] p new int[n]; int center 0, right 0; int maxLen 0, maxCenter 0; for (int i 0; i n; i) { if (i right) { int mirror 2 * center - i; p[i] Math.min(right - i, p[mirror]); } else { p[i] 1; } while (i - p[i] 0 i p[i] n t.charAt(i - p[i]) t.charAt(i p[i])) { p[i]; } if (i p[i] right) { right i p[i]; center i; } if (p[i] - 1 maxLen) { maxLen p[i] - 1; maxCenter i; } } int start (maxCenter - maxLen) / 2; return s.substring(start, start maxLen); }我们拿babad走一遍预处理后变成#b#a#b#a#d#。i3 对应字符a此时p[3] 1扩展发现t[2] t[4]即# #继续t[1] t[5]即b b继续t[0] t[6]即# #继续越界停止得p[3] 4。当 i7第二个a它落在以 3 为中心、半径为 4右边界 right7的已知回文里于是mirror 2*3-7 -1但right - i 0所以p[7]初始为 0 再扩展最终扩展到边界也不算很大。整个过程每个位置至多扩展一次均摊下来是线性复杂度。5.4 马拉车在面试中要不要主动写分情况讨论我的建议是除非面试官明确要求能否做到 O(n)否则面试现场默认不主动写 Manacher。理由有三个一是它代码比中心扩展长、变量多在没有充分熟练的情况下容易出 bug二是面试官真正想看的是你的思考过程知道有线性解法、能说出 Manacher 的核心思想预处理 回文半径复用已经能体现深度了三是很多面试官自己对这个算法也未必熟到能纠正你的错误你写错了他们也不一定能发现反而成了你背了一段没法自洽的代码的减分项。但如果是笔试环节或者目标公司明确爱考硬核算法比如某些大厂的白板环节Manacher 就是真正的区分度。你需要在面试前刷到十分钟内默写无误的程度并且能解释清楚为什么均摊是 O(n)——这个复杂度证明甚至可以当作你和面试官聊深度的加分话题。6. 实战细节测试用例设计、常见追问与代码习惯6.1 这类题目提交前必须自测的六组边界用例面试里写完之后面试官通常会让你手跑几个用例验证一下这时候你心里要有备选用例库而不是现场懵掉。我总结了一份覆盖度比较高的测试清单用例预期结果考察点a或返回原串长度 0 和 1 的边界ac返回a或c无回文时的默认值处理babad返回bab或aba奇数长度回文cbbd返回bb偶数长度回文aaaa返回aaaa全相同字符中心扩展的最大压力长度 1000 以上的随机串不超时复杂度的实际验证其中aaaa这个用例特别有意思中心扩展的 while 循环会从第一个中心一直扩展到末尾但正是因为每个中心扩展次数均摊下来是 O(n)总体依然是 O(n^2) 而不是 O(n^3)。有些候选人在这个用例上会疑惑中间很多重复扩展啊能解释清楚这一点面试官会觉得你对复杂度的理解是扎实的而不是背结论的。6.2 面试官最可能追着问的五个问题你想好怎么答了吗为什么中心扩展的复杂度是 O(n^2)答枚举 2n-1 个中心每个中心最多向外扩展 n 次最坏情况如aaaaa时每个中心的扩展步数分别是 1、2、3、4、5、4、3、2、1总和约 n^2/2所以是 O(n^2)。动态规划和中心扩展本质上有什么区别答两者都是在利用回文的子结构是回文这个性质中心扩展是自顶向下的收缩视角DP 是自底向上的递推视角DP 空间换时间虽然两者时间一样中心扩展省空间。能不能在 O(n log n) 内解决答可以用二分 滚动哈希Rabin-Karp对回文半径做二分查找但这个方案随机化且代码复杂度高确定性 O(n) 就是 Manacher。如果要返回所有最长回文子串怎么办答记录所有达到 maxLen 的起始位置再一次遍历收集即可注意去重。如果字符串可能包含中文甚至 emoji 呢答Java 里charAt是按 UTF-16 的 code unit 来取的emoji 是代理对surrogate pair直接 charAt 会拆坏这时候需要转成 code point 数组来处理。不过在 LeetCode 的题目语境下默认输入是 ascii 字符不必过度工程化但你主动说出这一点会加分。6.3 现场写代码的三个好习惯命名、防御、复杂度自述我想强调三个在面试中比算法本身更隐形加分的习惯。第一变量命名要有语义st、en、l、r不是不能用但start、end、left、right会让你在讲解时少很多口误。第二方法入口做防御性判断if (s null || s.length() 2)这一行不仅不是多余的反而是面试官重点关注的地方它代表你对空指针和边界条件的敏感性。第三写完代码先自己讲一遍复杂度再问面试官你有什么想问的不要等着面试官来问那是被动应答主动自述会显得你全局意识强。另外一个小技巧把expandAroundCenter拆成独立方法会让longestPalindrome主方法非常干净。面试官看代码第一眼是看结构再看细节结构清爽能给你的工程素养加分——这在学校里可能没人教你但大厂面试真的很吃这一套。我个人刷这道题的经验是先用中心扩展法做透再把动态规划和 Manacher 各写三遍直到能闭着眼把四种解法的时间复杂度、空间复杂度、适用场景像背乘法口诀一样说出来。这套功夫下完之后你会发现后面做 LeetCode 647 回文子串、LeetCode 516 最长回文子序列基本就是这道题思路的变体十分钟内能出解法。经典题的价值就在这——一道题打通一类题。