最近不少考研交流群里都在传“爱初心真题”系列里东华大学的这道题版本五花八门有说机试考过的有说面试被问到的。点开之后发现题目本身并不生僻甚至可以说是一道“老朋友”——求最长回文子串。但有意思的是很多同学第一反应是“这题我会”真拿笔在纸上写完整代码时却暴露了边界处理、复杂度分析、遍历顺序等一堆问题。我的判断很明确这道“东华大学真题”真正值得讨论的不是题目本身是否真的在某年考过而是它背后覆盖的算法能力梯度——从暴力枚举到动态规划从中心扩展到 Manacher 算法恰好构成了一条完整的字符串算法学习路径。搞懂这条路径将来再遇到任何回文类问题你都能在几秒内判断出“该用哪一层解法”。这篇文章会把四层解法全部拆开讲透给出完整 Java 代码、复杂度分析和考场选择建议并总结一套应对字符串真题的通用排查清单。建议收藏刷题和准备复试机试时随时可以翻出来对照。1. 这篇文章真正要解决的问题先说实话字符串题在算法面试和考研复试中有着特殊的“迷惑性”。链表、二叉树这类题目数据结构本身就拦住了很多人但字符串题不同它看起来谁都能下手可一旦进入细节就特别容易翻车。回文类问题更是如此。“最长回文子串”这道题在 LeetCode 上是第 5 题在牛客、力扣等平台都是热度极高的经典题。它之所以被高校机试反复引用是因为它有多个层次的解法能够一次性考查考生三件事能不能写出正确但慢的暴力解法会不会用动态规划建立状态转移并理解遍历顺序知不知道还有 O(n) 的线性做法以及它为什么快。换句话说这道题就是一面“照妖镜”你的算法功底到哪个层级代码一跑就清楚了。这篇文章适合三类读者准备考研复试、高校上机考试的计算机专业学生准备后端开发实习或校招面试想系统复盘字符串题型的同学刷过一些题但总感觉“看了就会、写了就错”想建立解题框架的读者。读完你将获得四套完整的 Java 解法代码一套复杂度与场景对比表以及一个通用的字符串题排查清单。2. 题目背景与核心概念本文采用 LeetCode 5 号题的标准描述作为题目模型这也是网络上流传版本中最高频的一种给你一个字符串s找到s中最长的回文子串。如果字符串的反序与原始字符串相同则该字符串称为回文字符串。示例输入s babad 输出bab 解释aba 同样是符合题意的答案。 输入s cbbd 输出bb搞懂这道题之前先把两个基础概念区分清楚回文串Palindrome正着读和反着读都一样的字符串。比如aba、aa、a都是回文串。单字符天然是回文串空串也通常被定义为回文串。子串Substring vs 子序列Subsequence子串必须是原字符串中连续的一段比如bab是babad的子串子序列则可以不连续比如bad是babad的子序列。本题目求的是子串不是子序列这一点看错会直接导致解题方向跑偏。题目还有几个隐含边界条件是机试中经常丢分的地方输入为空串时应返回空串输入长度为 1 时直接返回该字符如果存在多个答案返回任意一个即可LeetCode 判题会接受多个符合条件的结果。掌握这些边界之后下面开始搭建环境然后进入四层解法的拆解。3. 环境准备与前置条件本文所有代码使用 Java 编写不依赖任何第三方框架Java 8 及以上版本均可运行。推荐使用 JDK 11 或 JDK 17 这类长期支持版本编译器选择 IDEA、Eclipse 或者直接在命令行用 OpenJDK 加文本编辑器都不会影响结果。本地快速验证的思路很简单新建一个名为Main.java的文件将各小节中的longestPalindrome方法和main方法粘贴进去执行javac Main.java编译执行java Main查看输出。如果你的环境没有安装 JDK也可以直接使用 LeetCode 中文站或牛客网的在线编辑器把longestPalindrome方法体粘贴进去提交验证。环境本身不是这道题的考查重点重点是先把算法思路跑通再回到在线平台确认边界用例。4. 解法一暴力枚举——先拿到基线拿到这道题最直观的想法是什么把字符串的所有子串都枚举出来逐个判断是不是回文串然后记录最长的那个。这个思路完全没有错。它是所有后续优化解法的“基线”——先保证能算对再谈算得快。完整代码如下// 文件名Main.java public class Main { // 判断 s[left..right] 这一段是否是回文串 private static boolean isPalindrome(String s, int left, int right) { while (left right) { if (s.charAt(left) ! s.charAt(right)) { return false; } left; right--; } return true; } public static String longestPalindrome(String s) { int n s.length(); if (n 2) { return s; } int maxLen 1; int begin 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; begin i; } } } return s.substring(begin, begin maxLen); } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果bab bb a暴力解法的代码量很少逻辑也直接但它的性能明显不够好。复杂度分析枚举所有子串需要双重循环循环次数约为 n²/2每次判断回文串时最坏情况要比较 n/2 对字符因此总时间复杂度为 O(n³)空间复杂度为 O(1)只用到了几个普通变量。当 n 1000 时n³ 是 10 亿级别机试中必然超时当 n 100 时100 万级别操作可以接受。所以暴力法的价值在于它适合快速验证思路也适合数据规模极小的场景但不适合作为考场最终提交答案。这里真正值得记下的经验是即使使用暴力法也要注意提前处理空串和单字符两种情况否则下面这类用例会在考试时白白丢分。5. 解法二动态规划——理解状态与遍历顺序暴力法慢在两点一是枚举太多子串二是每个子串都要从头比较。动态规划的思路就是用一张二维表把已经计算过的结果存下来避免重复判断。这个思路的关键是找出状态转移关系。先定义状态dp[i][j]表示字符串从下标i到下标j这一段是否是回文串值为true或false。那么一段子串s[i..j]是回文串需要满足什么条件首尾字符相同s.charAt(i) s.charAt(j)去掉首尾后剩余部分s[i1..j-1]也必须是回文串或者这段子串的长度小于等于 2即j - i 2此时只要首尾相同就一定是回文串。把上面三条整理成状态转移方程dp[i][j] (s.charAt(i) s.charAt(j)) (j - i 2 || dp[i 1][j - 1])初始化也很简单任何长度为 1 的子串都是回文串即dp[i][i] true。这里真正容易踩坑的地方是遍历顺序。很多初学者会写成普通的两层循环从i从 0 到 n、j从 i 到 n。这样写是有问题的因为计算dp[i][j]时需要依赖dp[i1][j-1]也就是长度更短的子串的结果。如果我们没有先把短子串全部计算完长一点的状态就拿不到正确值。正确的做法是按子串长度从小到大遍历。先算长度为 1 的再算长度为 2 的然后依次递增。完整代码如下// 文件名Main.java public class Main { public static String longestPalindrome(String s) { int n s.length(); if (n 2) { return s; } boolean[][] dp new boolean[n][n]; int maxLen 1; int begin 0; // 长度为 1 的子串都是回文串 for (int i 0; i n; i) { dp[i][i] true; } char[] arr s.toCharArray(); // 按子串长度从小到大枚举 for (int len 2; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; if (arr[i] ! arr[j]) { dp[i][j] false; } else { if (len 2) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } if (dp[i][j] len maxLen) { maxLen len; begin i; } } } return s.substring(begin, begin maxLen); } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果bab bb a复杂度分析时间复杂度 O(n²)需要填满一张 n × n 的表空间复杂度 O(n²)因为我们需要保存整张二维状态表。动态规划在“最长回文子串”这个场景中最大的优势是思路直观、好推导适合在面试时展示逻辑推导能力缺点是需要 O(n²) 的额外空间。如果题目要求的不是“返回最长回文子串”而是“统计一共有多少个回文子串”DP 的思路会更加常用这也是它长期被视为回文题“基础解法”的原因。6. 解法三中心扩展——考场最稳的写法动态规划的思路已经不错了但能否把空间优化到 O(1)可以。这次换一个角度想问题回文串的本质是对称。既然它是对称的那就可以从一个“中心点”开始向两边扩展只要两边字符相等就继续扩大范围。需要特别注意的是回文中心有两种情况奇数长度回文串中心是单个字符例如aba的中心是b偶数长度回文串中心是两个字符之间的空隙例如bb的中心在b和b之间。因此枚举中心点时必须同时对这两种情况做扩展并取两者中较长的结果。完整代码如下// 文件名Main.java public class Main { public static String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int start 0; int end 0; for (int i 0; i s.length(); i) { // 奇数长度回文中心为 i int len1 expandAroundCenter(s, i, i); // 偶数长度回文中心为 i 和 i1 之间 int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len end - start) { start i - (len - 1) / 2; end i len / 2; } } return s.substring(start, end 1); } private static int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } // 扩展结束后left 和 right 指向的是越界字符或左右不等的字符 // 回文串长度是 (right - left - 1) return right - left - 1; } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果与前面一致bab bb a复杂度分析时间复杂度 O(n²)每个中心向两边扩展约 n/2 次一共有 2n-1 个中心空间复杂度 O(1)只用了常数额外空间。中心扩展这个解法是我在考场或面试时最推荐的版本原因有三代码量小逻辑简单不容易在紧张状态下写错空间复杂度是 O(1)比 DP 省内存遇到奇偶回文时只要用一个辅助方法处理两个中心参数即可思路非常清晰。如果只能记住一种解法应对机试我会先记中心扩展。7. 解法四Manacher 算法——O(n) 的最优解前面三个解法的最高时间复杂度都是 O(n²)。那么能不能做到 O(n)能。这就是 Manacher 算法中文通常翻译为“马拉车算法”。它的核心思想是利用回文串的对称性减少中心扩展过程中重复的比较。这个算法的推导有一定难度但代码模板比较固定。如果你刷题目标是“AC”记住模板即可如果你想真正理解它建议配合画图推导一遍。Manacher 的第一步是预处理字符串。为了统一处理奇偶长度回文我们在每个字符之间插入一个特殊分隔符例如#并在首尾加上哨兵字符例如^和$避免扩展时反复判断越界。比如原始串babad预处理后变成^#b#a#b#a#d#$接着维护几个关键变量p[i]以预处理后字符串的第 i 位为中心可以扩展出去的臂长不包含中心本身center当前已知最右回文串的中心位置right当前已知最右回文串能覆盖到的最右边界。算法在遍历过程中如果当前中心i在right左侧说明可以利用对称位置mirror 2 * center - i的臂长来初始化p[i]从而减少重复扩展。如果i在right右侧就只能从 1 开始逐步扩展。完整代码如下// 文件名Main.java public class Main { public static String longestPalindrome(String s) { if (s null || s.length() 0) { return ; } // 预处理^ 和 $ 是哨兵避免边界判断 StringBuilder sb new StringBuilder(); sb.append(^); for (int i 0; i s.length(); i) { sb.append(#); sb.append(s.charAt(i)); } sb.append(#); sb.append($); char[] chars sb.toString().toCharArray(); int n chars.length; int[] p new int[n]; int center 0; int right 0; int maxLen 0; int startIndex 0; // 首尾哨兵不需要参与计算 for (int i 1; i n - 1; i) { if (i right) { int mirror 2 * center - i; p[i] Math.min(right - i, p[mirror]); } // 尝试向两边扩展 while (chars[i p[i] 1] chars[i - p[i] - 1]) { p[i]; } // 更新最右回文串的 center 和 right if (i p[i] right) { center i; right i p[i]; } // 记录最长回文串 if (p[i] maxLen) { maxLen p[i]; startIndex (i - p[i]) / 2; } } return s.substring(startIndex, startIndex maxLen); } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果同样稳定输出bab bb a复杂度分析时间复杂度 O(n)每个字符最多被扩展比较一次空间复杂度 O(n)因为需要保存预处理串和臂长数组。这里有一个很实在的考场建议如果对 Manacher 模板不够熟练笔试时不要强行写。因为它的代码细节多一旦写错调试时间远大于前面的中心扩展解法。更合理的策略是先用中心扩展解法通过大部分用例把 Manacher 作为学习和面试讲思路时的亮点来准备而不是作为考场默认工具。8. 四种解法对比与考场选择建议四种解法全部讲完了现在用一张表从时间、空间、代码量、适用场景四个维度做横向对比。解法时间复杂度空间复杂度代码量适用场景暴力枚举O(n³)O(1)很少n 很小约 100 以内用于快速验证思路动态规划O(n²)O(n²)中等需要回文子串计数等问题适合面试推导中心扩展O(n²)O(1)少常规机试与面试首选代码简单且不易错ManacherO(n)O(n)较多追求线性时间或阅读源码时理解优化思路具体选择上可以按字符串长度来判断n 100暴力法完全可行写起来最快100 n 1000机试常见范围中心扩展最稳DP 也可以1000 n 100000中心扩展在部分评测中会偏慢Manacher 更保险面试场景先讲清楚暴力解和 DP再提到中心扩展和 Manacher展示出复杂度阶梯意识。我见过不少同学走进一个误区一上来就背 Manacher遇到回文题就先写马拉车结果在字符串长度只有 50 的题目上代码写错后调试了二十分钟。这个教训值得记住没有绝对最优的解法只有最合适当前场景的解法。9. 常见问题与排查思路回文串题目的细节多以下是我整理的高频问题排查表覆盖了本地运行和在线提交中常见的坑。问题现象可能原因排查方式解决方案输入为空串时报错未处理n 2或空串分支在方法开头打印n或做空值判断方法入口统一处理s null和s.length() 1输入单字符时返回空串返回值覆盖了初始化结果先检查n 2直接返回s确保单字符分支在核心逻辑之前返回DP 解法结果不对遍历顺序写成了普通双层循环打印dp表观察依赖项改为按子串长度从小到大遍历中心扩展结果少一个字符end与start更新边界计算错误用aba、bb等小样例单步调试回文串长度与(len - 1) / 2、len / 2的换算公式要记住全相同字符时性能很差算法本身复杂度较高用例刚好命中观察超时用例长度长度很大时改用 Manacher 或中心扩展Manacher 出现数组越界没有在预处理串首尾加哨兵检查^和$是否存在预处理字符串必须包含首尾哨兵字符多个答案时结果和题目示例不一致判定逻辑取最长但方向与示例不同打印begin和maxLenLeetCode 允许多答案只要长度正确即可一个通用的调试思路是本地跑通后不要直接提交先在主函数里手动测试四类特殊输入空字符串单字符串类似aaaa的全相同字符串类似ab这类完全不是回文的字符串。这四个用例可以覆盖大多数边界错误。10. 真题应对最佳实践与延伸学习聊完解法最后回到“真题”本身。很多同学拿到一道流传出来的题目第一反应是“我要把这题原样背下来”。这个策略比较低效因为真题在传播过程中常常会改输入输出格式、改数据范围甚至把“最长回文子串”改成“回文子串数量”。更好的做法是建立一套自己的字符串题应对清单遇到任何相关真题时按顺序检查。推荐检查顺序确认输入是否可能为空串或null确认返回结果是子串还是子序列确认返回值是子串本身还是子串长度确认字符串的数据范围这决定了复杂度上限确认字符集范围是全小写字母还是 ASCII还是 Unicode确认有多个合法答案时题目是否对答案位置有偏好先写最小可运行的解法再根据数据范围决定是否优化。机试现场还有几条实用策略先在注释里写清楚题目要求、复杂度目标、核心思路再写代码避免写着写着忘掉方向优先提交中心扩展版本因为它能在绝大多数数据范围内通过如果数据范围提示你要用 O(n) 解法再考虑 Manacher不要在一个题上花超过半小时调试尤其不要试图现场推导 Manacher 的对称性。这道题学完之后可以沿着回文专题继续延伸推荐几个高频题回文子串数量统计LeetCode 647中心扩展和 DP 都能解最长回文子序列LeetCode 516注意是子序列DP 思路会有区别验证回文串LeetCode 125考察字符串过滤与双指针最短回文串LeetCode 214综合了字符串匹配与回文难度更高。建议按“暴力 → DP → 中心扩展 → Manacher”的顺序逐个吃透不要跳过中间步骤。刷题最怕的不是题难而是只背结论、不建体系。11. 总结这道题真正在考什么现在回头再看东华大学流传的这道“你会做吗”会发现它其实是一个很好的算法能力测试样本。表面上它只考“最长回文子串”实际上考的是你看到字符串题后能不能快速判断出可用的算法层级能不能写出边界完整、复杂度合理的代码能不能在数据规模变化时换用不同解法的工程判断力。四层解法之间的关系也很清楚暴力法帮助你建立基线和熟悉题目动态规划帮助你理解状态转移和遍历顺序中心扩展是考场上的稳定输出Manacher 则是你算法视野的上限。每一层都不是孤立的它们共同构成了一条完整的、可复用的解题路径。这道题你之前会做吗如果会希望你这一次能从“会做”升级为“会系统地做”如果不会现在你已经有了四种思路和完整的 Java 代码照着跑一遍再对照最后的排查清单做几道延伸题会比单纯背答案有效得多。建议收藏本文等下次再遇到回文类真题时翻回来看一眼这张复杂度对比表就够了。
最长回文子串全解：从暴力到Manacher的字符串算法进阶
最近不少考研交流群里都在传“爱初心真题”系列里东华大学的这道题版本五花八门有说机试考过的有说面试被问到的。点开之后发现题目本身并不生僻甚至可以说是一道“老朋友”——求最长回文子串。但有意思的是很多同学第一反应是“这题我会”真拿笔在纸上写完整代码时却暴露了边界处理、复杂度分析、遍历顺序等一堆问题。我的判断很明确这道“东华大学真题”真正值得讨论的不是题目本身是否真的在某年考过而是它背后覆盖的算法能力梯度——从暴力枚举到动态规划从中心扩展到 Manacher 算法恰好构成了一条完整的字符串算法学习路径。搞懂这条路径将来再遇到任何回文类问题你都能在几秒内判断出“该用哪一层解法”。这篇文章会把四层解法全部拆开讲透给出完整 Java 代码、复杂度分析和考场选择建议并总结一套应对字符串真题的通用排查清单。建议收藏刷题和准备复试机试时随时可以翻出来对照。1. 这篇文章真正要解决的问题先说实话字符串题在算法面试和考研复试中有着特殊的“迷惑性”。链表、二叉树这类题目数据结构本身就拦住了很多人但字符串题不同它看起来谁都能下手可一旦进入细节就特别容易翻车。回文类问题更是如此。“最长回文子串”这道题在 LeetCode 上是第 5 题在牛客、力扣等平台都是热度极高的经典题。它之所以被高校机试反复引用是因为它有多个层次的解法能够一次性考查考生三件事能不能写出正确但慢的暴力解法会不会用动态规划建立状态转移并理解遍历顺序知不知道还有 O(n) 的线性做法以及它为什么快。换句话说这道题就是一面“照妖镜”你的算法功底到哪个层级代码一跑就清楚了。这篇文章适合三类读者准备考研复试、高校上机考试的计算机专业学生准备后端开发实习或校招面试想系统复盘字符串题型的同学刷过一些题但总感觉“看了就会、写了就错”想建立解题框架的读者。读完你将获得四套完整的 Java 解法代码一套复杂度与场景对比表以及一个通用的字符串题排查清单。2. 题目背景与核心概念本文采用 LeetCode 5 号题的标准描述作为题目模型这也是网络上流传版本中最高频的一种给你一个字符串s找到s中最长的回文子串。如果字符串的反序与原始字符串相同则该字符串称为回文字符串。示例输入s babad 输出bab 解释aba 同样是符合题意的答案。 输入s cbbd 输出bb搞懂这道题之前先把两个基础概念区分清楚回文串Palindrome正着读和反着读都一样的字符串。比如aba、aa、a都是回文串。单字符天然是回文串空串也通常被定义为回文串。子串Substring vs 子序列Subsequence子串必须是原字符串中连续的一段比如bab是babad的子串子序列则可以不连续比如bad是babad的子序列。本题目求的是子串不是子序列这一点看错会直接导致解题方向跑偏。题目还有几个隐含边界条件是机试中经常丢分的地方输入为空串时应返回空串输入长度为 1 时直接返回该字符如果存在多个答案返回任意一个即可LeetCode 判题会接受多个符合条件的结果。掌握这些边界之后下面开始搭建环境然后进入四层解法的拆解。3. 环境准备与前置条件本文所有代码使用 Java 编写不依赖任何第三方框架Java 8 及以上版本均可运行。推荐使用 JDK 11 或 JDK 17 这类长期支持版本编译器选择 IDEA、Eclipse 或者直接在命令行用 OpenJDK 加文本编辑器都不会影响结果。本地快速验证的思路很简单新建一个名为Main.java的文件将各小节中的longestPalindrome方法和main方法粘贴进去执行javac Main.java编译执行java Main查看输出。如果你的环境没有安装 JDK也可以直接使用 LeetCode 中文站或牛客网的在线编辑器把longestPalindrome方法体粘贴进去提交验证。环境本身不是这道题的考查重点重点是先把算法思路跑通再回到在线平台确认边界用例。4. 解法一暴力枚举——先拿到基线拿到这道题最直观的想法是什么把字符串的所有子串都枚举出来逐个判断是不是回文串然后记录最长的那个。这个思路完全没有错。它是所有后续优化解法的“基线”——先保证能算对再谈算得快。完整代码如下// 文件名Main.java public class Main { // 判断 s[left..right] 这一段是否是回文串 private static boolean isPalindrome(String s, int left, int right) { while (left right) { if (s.charAt(left) ! s.charAt(right)) { return false; } left; right--; } return true; } public static String longestPalindrome(String s) { int n s.length(); if (n 2) { return s; } int maxLen 1; int begin 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; begin i; } } } return s.substring(begin, begin maxLen); } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果bab bb a暴力解法的代码量很少逻辑也直接但它的性能明显不够好。复杂度分析枚举所有子串需要双重循环循环次数约为 n²/2每次判断回文串时最坏情况要比较 n/2 对字符因此总时间复杂度为 O(n³)空间复杂度为 O(1)只用到了几个普通变量。当 n 1000 时n³ 是 10 亿级别机试中必然超时当 n 100 时100 万级别操作可以接受。所以暴力法的价值在于它适合快速验证思路也适合数据规模极小的场景但不适合作为考场最终提交答案。这里真正值得记下的经验是即使使用暴力法也要注意提前处理空串和单字符两种情况否则下面这类用例会在考试时白白丢分。5. 解法二动态规划——理解状态与遍历顺序暴力法慢在两点一是枚举太多子串二是每个子串都要从头比较。动态规划的思路就是用一张二维表把已经计算过的结果存下来避免重复判断。这个思路的关键是找出状态转移关系。先定义状态dp[i][j]表示字符串从下标i到下标j这一段是否是回文串值为true或false。那么一段子串s[i..j]是回文串需要满足什么条件首尾字符相同s.charAt(i) s.charAt(j)去掉首尾后剩余部分s[i1..j-1]也必须是回文串或者这段子串的长度小于等于 2即j - i 2此时只要首尾相同就一定是回文串。把上面三条整理成状态转移方程dp[i][j] (s.charAt(i) s.charAt(j)) (j - i 2 || dp[i 1][j - 1])初始化也很简单任何长度为 1 的子串都是回文串即dp[i][i] true。这里真正容易踩坑的地方是遍历顺序。很多初学者会写成普通的两层循环从i从 0 到 n、j从 i 到 n。这样写是有问题的因为计算dp[i][j]时需要依赖dp[i1][j-1]也就是长度更短的子串的结果。如果我们没有先把短子串全部计算完长一点的状态就拿不到正确值。正确的做法是按子串长度从小到大遍历。先算长度为 1 的再算长度为 2 的然后依次递增。完整代码如下// 文件名Main.java public class Main { public static String longestPalindrome(String s) { int n s.length(); if (n 2) { return s; } boolean[][] dp new boolean[n][n]; int maxLen 1; int begin 0; // 长度为 1 的子串都是回文串 for (int i 0; i n; i) { dp[i][i] true; } char[] arr s.toCharArray(); // 按子串长度从小到大枚举 for (int len 2; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; if (arr[i] ! arr[j]) { dp[i][j] false; } else { if (len 2) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } if (dp[i][j] len maxLen) { maxLen len; begin i; } } } return s.substring(begin, begin maxLen); } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果bab bb a复杂度分析时间复杂度 O(n²)需要填满一张 n × n 的表空间复杂度 O(n²)因为我们需要保存整张二维状态表。动态规划在“最长回文子串”这个场景中最大的优势是思路直观、好推导适合在面试时展示逻辑推导能力缺点是需要 O(n²) 的额外空间。如果题目要求的不是“返回最长回文子串”而是“统计一共有多少个回文子串”DP 的思路会更加常用这也是它长期被视为回文题“基础解法”的原因。6. 解法三中心扩展——考场最稳的写法动态规划的思路已经不错了但能否把空间优化到 O(1)可以。这次换一个角度想问题回文串的本质是对称。既然它是对称的那就可以从一个“中心点”开始向两边扩展只要两边字符相等就继续扩大范围。需要特别注意的是回文中心有两种情况奇数长度回文串中心是单个字符例如aba的中心是b偶数长度回文串中心是两个字符之间的空隙例如bb的中心在b和b之间。因此枚举中心点时必须同时对这两种情况做扩展并取两者中较长的结果。完整代码如下// 文件名Main.java public class Main { public static String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int start 0; int end 0; for (int i 0; i s.length(); i) { // 奇数长度回文中心为 i int len1 expandAroundCenter(s, i, i); // 偶数长度回文中心为 i 和 i1 之间 int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len end - start) { start i - (len - 1) / 2; end i len / 2; } } return s.substring(start, end 1); } private static int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } // 扩展结束后left 和 right 指向的是越界字符或左右不等的字符 // 回文串长度是 (right - left - 1) return right - left - 1; } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果与前面一致bab bb a复杂度分析时间复杂度 O(n²)每个中心向两边扩展约 n/2 次一共有 2n-1 个中心空间复杂度 O(1)只用了常数额外空间。中心扩展这个解法是我在考场或面试时最推荐的版本原因有三代码量小逻辑简单不容易在紧张状态下写错空间复杂度是 O(1)比 DP 省内存遇到奇偶回文时只要用一个辅助方法处理两个中心参数即可思路非常清晰。如果只能记住一种解法应对机试我会先记中心扩展。7. 解法四Manacher 算法——O(n) 的最优解前面三个解法的最高时间复杂度都是 O(n²)。那么能不能做到 O(n)能。这就是 Manacher 算法中文通常翻译为“马拉车算法”。它的核心思想是利用回文串的对称性减少中心扩展过程中重复的比较。这个算法的推导有一定难度但代码模板比较固定。如果你刷题目标是“AC”记住模板即可如果你想真正理解它建议配合画图推导一遍。Manacher 的第一步是预处理字符串。为了统一处理奇偶长度回文我们在每个字符之间插入一个特殊分隔符例如#并在首尾加上哨兵字符例如^和$避免扩展时反复判断越界。比如原始串babad预处理后变成^#b#a#b#a#d#$接着维护几个关键变量p[i]以预处理后字符串的第 i 位为中心可以扩展出去的臂长不包含中心本身center当前已知最右回文串的中心位置right当前已知最右回文串能覆盖到的最右边界。算法在遍历过程中如果当前中心i在right左侧说明可以利用对称位置mirror 2 * center - i的臂长来初始化p[i]从而减少重复扩展。如果i在right右侧就只能从 1 开始逐步扩展。完整代码如下// 文件名Main.java public class Main { public static String longestPalindrome(String s) { if (s null || s.length() 0) { return ; } // 预处理^ 和 $ 是哨兵避免边界判断 StringBuilder sb new StringBuilder(); sb.append(^); for (int i 0; i s.length(); i) { sb.append(#); sb.append(s.charAt(i)); } sb.append(#); sb.append($); char[] chars sb.toString().toCharArray(); int n chars.length; int[] p new int[n]; int center 0; int right 0; int maxLen 0; int startIndex 0; // 首尾哨兵不需要参与计算 for (int i 1; i n - 1; i) { if (i right) { int mirror 2 * center - i; p[i] Math.min(right - i, p[mirror]); } // 尝试向两边扩展 while (chars[i p[i] 1] chars[i - p[i] - 1]) { p[i]; } // 更新最右回文串的 center 和 right if (i p[i] right) { center i; right i p[i]; } // 记录最长回文串 if (p[i] maxLen) { maxLen p[i]; startIndex (i - p[i]) / 2; } } return s.substring(startIndex, startIndex maxLen); } public static void main(String[] args) { System.out.println(longestPalindrome(babad)); System.out.println(longestPalindrome(cbbd)); System.out.println(longestPalindrome(a)); System.out.println(longestPalindrome()); } }运行结果同样稳定输出bab bb a复杂度分析时间复杂度 O(n)每个字符最多被扩展比较一次空间复杂度 O(n)因为需要保存预处理串和臂长数组。这里有一个很实在的考场建议如果对 Manacher 模板不够熟练笔试时不要强行写。因为它的代码细节多一旦写错调试时间远大于前面的中心扩展解法。更合理的策略是先用中心扩展解法通过大部分用例把 Manacher 作为学习和面试讲思路时的亮点来准备而不是作为考场默认工具。8. 四种解法对比与考场选择建议四种解法全部讲完了现在用一张表从时间、空间、代码量、适用场景四个维度做横向对比。解法时间复杂度空间复杂度代码量适用场景暴力枚举O(n³)O(1)很少n 很小约 100 以内用于快速验证思路动态规划O(n²)O(n²)中等需要回文子串计数等问题适合面试推导中心扩展O(n²)O(1)少常规机试与面试首选代码简单且不易错ManacherO(n)O(n)较多追求线性时间或阅读源码时理解优化思路具体选择上可以按字符串长度来判断n 100暴力法完全可行写起来最快100 n 1000机试常见范围中心扩展最稳DP 也可以1000 n 100000中心扩展在部分评测中会偏慢Manacher 更保险面试场景先讲清楚暴力解和 DP再提到中心扩展和 Manacher展示出复杂度阶梯意识。我见过不少同学走进一个误区一上来就背 Manacher遇到回文题就先写马拉车结果在字符串长度只有 50 的题目上代码写错后调试了二十分钟。这个教训值得记住没有绝对最优的解法只有最合适当前场景的解法。9. 常见问题与排查思路回文串题目的细节多以下是我整理的高频问题排查表覆盖了本地运行和在线提交中常见的坑。问题现象可能原因排查方式解决方案输入为空串时报错未处理n 2或空串分支在方法开头打印n或做空值判断方法入口统一处理s null和s.length() 1输入单字符时返回空串返回值覆盖了初始化结果先检查n 2直接返回s确保单字符分支在核心逻辑之前返回DP 解法结果不对遍历顺序写成了普通双层循环打印dp表观察依赖项改为按子串长度从小到大遍历中心扩展结果少一个字符end与start更新边界计算错误用aba、bb等小样例单步调试回文串长度与(len - 1) / 2、len / 2的换算公式要记住全相同字符时性能很差算法本身复杂度较高用例刚好命中观察超时用例长度长度很大时改用 Manacher 或中心扩展Manacher 出现数组越界没有在预处理串首尾加哨兵检查^和$是否存在预处理字符串必须包含首尾哨兵字符多个答案时结果和题目示例不一致判定逻辑取最长但方向与示例不同打印begin和maxLenLeetCode 允许多答案只要长度正确即可一个通用的调试思路是本地跑通后不要直接提交先在主函数里手动测试四类特殊输入空字符串单字符串类似aaaa的全相同字符串类似ab这类完全不是回文的字符串。这四个用例可以覆盖大多数边界错误。10. 真题应对最佳实践与延伸学习聊完解法最后回到“真题”本身。很多同学拿到一道流传出来的题目第一反应是“我要把这题原样背下来”。这个策略比较低效因为真题在传播过程中常常会改输入输出格式、改数据范围甚至把“最长回文子串”改成“回文子串数量”。更好的做法是建立一套自己的字符串题应对清单遇到任何相关真题时按顺序检查。推荐检查顺序确认输入是否可能为空串或null确认返回结果是子串还是子序列确认返回值是子串本身还是子串长度确认字符串的数据范围这决定了复杂度上限确认字符集范围是全小写字母还是 ASCII还是 Unicode确认有多个合法答案时题目是否对答案位置有偏好先写最小可运行的解法再根据数据范围决定是否优化。机试现场还有几条实用策略先在注释里写清楚题目要求、复杂度目标、核心思路再写代码避免写着写着忘掉方向优先提交中心扩展版本因为它能在绝大多数数据范围内通过如果数据范围提示你要用 O(n) 解法再考虑 Manacher不要在一个题上花超过半小时调试尤其不要试图现场推导 Manacher 的对称性。这道题学完之后可以沿着回文专题继续延伸推荐几个高频题回文子串数量统计LeetCode 647中心扩展和 DP 都能解最长回文子序列LeetCode 516注意是子序列DP 思路会有区别验证回文串LeetCode 125考察字符串过滤与双指针最短回文串LeetCode 214综合了字符串匹配与回文难度更高。建议按“暴力 → DP → 中心扩展 → Manacher”的顺序逐个吃透不要跳过中间步骤。刷题最怕的不是题难而是只背结论、不建体系。11. 总结这道题真正在考什么现在回头再看东华大学流传的这道“你会做吗”会发现它其实是一个很好的算法能力测试样本。表面上它只考“最长回文子串”实际上考的是你看到字符串题后能不能快速判断出可用的算法层级能不能写出边界完整、复杂度合理的代码能不能在数据规模变化时换用不同解法的工程判断力。四层解法之间的关系也很清楚暴力法帮助你建立基线和熟悉题目动态规划帮助你理解状态转移和遍历顺序中心扩展是考场上的稳定输出Manacher 则是你算法视野的上限。每一层都不是孤立的它们共同构成了一条完整的、可复用的解题路径。这道题你之前会做吗如果会希望你这一次能从“会做”升级为“会系统地做”如果不会现在你已经有了四种思路和完整的 Java 代码照着跑一遍再对照最后的排查清单做几道延伸题会比单纯背答案有效得多。建议收藏本文等下次再遇到回文类真题时翻回来看一眼这张复杂度对比表就够了。