企业官网建设流程全解析

回文子串这四个字，在我刚开始刷 LeetCode 的时候曾经是噩梦。什么“最长回文子串”“回文子串个数”“分割回文串”，题目看着都不长，真上手就是各种超时和数组越界。后来花了一整周专门拉通这个专题，发现它其实是字符串算法里套路感最强的一类：只要吃透中心扩展、动态规划回文表和马拉车算法这三板斧，大部分回文题都能在五分钟内定出解法框架。

这篇笔记是我自己在 Java 环境下的完整刷题总结，从最朴素的暴力思路讲起，一直推到 O(n) 的马拉车解法，每个关键步骤都配了完整的 Java 代码和踩坑记录。内容覆盖 LeetCode 第 5 题、第 647 题、第 131 题这些高频题，也顺带整理了相关变种题的练习思路。适合正在刷 LeetCode 热门 100 题、准备 Java 后端面试，或者想系统补一补字符串算法的同学直接拿去对照复习。

1. 回文子串题的本质：三种问法，一条底层能力

1.1 先理解“回文子串”到底在考察什么

回文串的定义很简单：一个字符串正着读和倒着读完全一样，比如"aba"、"aa"、"abba"都是回文串，而"ab"、"abc"不是。回文子串问题就是在给定字符串s中，找出所有满足这个性质的连续子串s[i..j]。

面试官喜欢拿这类题来面，是因为它一个题目同时压中了好几个基本功：双指针思想、动态规划状态设计、递归回溯的切割逻辑，以及字符串索引的精细控制。你只要有一个环节不扎实，代码就会在边界条件上翻车。而且这类题可以用多种解法做，不同解法的复杂度差异很大，很能考察候选人对“暴力解法为什么慢”“如何通过空间换时间”的理解程度。

实际面试里，回文子串的出现频率远高于你的想象。你翻一下 LeetCode 热门 100 题，里面至少有五六道题和回文相关。我做后端开发这些年，在多家公司的笔试题里都见过变种：有的是判断回文链表，有的是求回文子串个数，有的是让字符串变成回文串的最小插入次数。核心逃不出这个专题。

1.2 高频回文题的三种分类

回文子串题目看起来多，本质上只有三类问法。我把它们整理成了一张表，方便你建立起初步的题型地图。

这三种问法看起来差异很大，但它们的底层能力是同一个：判断任意子串s[i..j]是否是回文串。只要把这句话想明白，接下来所有的解法都是围绕“如何高效完成这个判断”展开的。

后面的章节我会按“先基础、再进阶、最后优化”的顺序来写。第二章先说中心扩展法，这是理解所有后续解法的基础；第三章讲动态规划回文表，它专门服务于数个数和分割类问题；第四章讲马拉车算法，这是追求极致性能的进阶武器；最后一章集中讲我在刷题过程中踩过的坑，以及一些面试角度的个人心得。

2. 中心扩展法：最长回文子串的基础解法

2.1 暴力解法为什么一定会超时

刚开始刷题的人容易写出最直观的暴力版本：枚举所有子串s[i..j]，再对每个子串调用isPalindrome()方法逐字符判断是否回文。这样出来的代码虽然逻辑没错，但复杂度是 O(n^3)，因为枚举本身要 O(n^2)，每次判断又要 O(n)。

以 LeetCode 5 为例，题目的字符串长度最多 1000。O(n^3) 在最坏情况下要执行约 10 亿次字符比较，在 Java 这种运行环境下几乎不可能通过。即便你能过，也说明测试数据太温柔，面试官如果追问一句“怎么优化”，你还是得回到更优的解法上来。所以暴力代码我建议你只作为思考起点，不要真的提交。

暴力解法还有一个隐藏问题：每次判断回文都重复扫描了大量字符。比如你判断完s[1..5]是回文，接着判断s[2..6]时，中间的对称关系完全可以用更巧妙的方式复用，但暴力写法完全没有利用这一点。

2.2 中心扩展的核心思想

中心扩展法的出发点很朴素：每个回文串都有一个“中心”。奇数长度的回文串中心是一个字符，比如"aba"的中心是b；偶数长度的回文串中心是相邻的两个字符，比如"abba"的中心是bb中间这条缝隙。

所以我们可以枚举每一个可能作为中心的位置，然后从这个中心向左右两边同时扩展，只要两侧字符相等，就说明回文串还能继续变长；一旦遇到两侧字符不同，就停下来，记录当前中心能扩展出的最大回文长度。

注意奇数和偶数两种情况都要枚举。一个字符本身可以看作奇数长度的回文串，所以奇数中心就是[i, i]；偶数中心则是[i, i+1]这对相邻字符。漏掉任何一个，都会导致结果偏短。

这里有一个很值得品味的关键点：中心扩展法把“判断所有子串是否回文”这个问题，转换成了“从所有中心出发找最远回文半径”的问题。它的复杂度是 O(n^2)，因为中心有大约 2n 个，每个中心扩展一次能走多长取决于回文串的长度，最坏情况下（比如所有字符都相同）每个中心都会扩展到字符串边缘。

2.3 最长回文子串：LeetCode 5 的 Java 完整实现

LeetCode 5 要求返回最长回文子串本身。我的实现思路是记录最长回文的起始位置和长度，最后用substring截取。完整代码如下：

class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) { return ""; } int start = 0; int maxLen = 0; for (int i = 0; i < s.length(); i++) { // 奇数长度回文，中心为 i int len1 = expandAroundCenter(s, i, i); // 偶数长度回文，中心为 i 和 i+1 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++; } // 循环结束时 left 和 right 比实际回文区间各多跨了一步 return right - left - 1; } }

这里最容易被搞错的就是start的推导。假设中心位置是i，回文长度是len，那么区间应该是[i - (len-1)/2, i + len/2]。比如"aba"，中心i=1，len=3，起点是1 - (3-1)/2 = 0；如果回文是"abba"，中心取在i=2和i+1=3的缝隙位置时，我们记录的i其实是左中心字符b，len=4，起点2 - (4-1)/2 = 0，依然正确。这个公式不需要死记，画两个例子就能验证。

expandAroundCenter返回right - left - 1也是一个经典陷阱。因为while循环退出时，left已经多往左移了一位，right已经多往右移了一位，所以真实回文区间长度应该是(right - 1) - (left + 1) + 1 = right - left - 1。我总是建议小伙伴在本地把这行代码打印一下，你会对“退出条件是失败条件”有更深的理解。

2.4 中心扩展法的延伸使用

中心扩展法不只能求最长回文子串，求回文子串个数也非常顺手，LeetCode 647 就是一个典型。每当一个中心扩展出长度为len的回文区间，就意味着这个中心贡献了一个新的回文子串。枚举所有中心，把每次扩展计数累加起来即可。代码如下：

class Solution { public int countSubstrings(String s) { if (s == null || s.length() == 0) { return 0; } int count = 0; for (int i = 0; i < s.length(); i++) { // 奇数中心 count += expandAndCount(s, i, i); // 偶数中心 count += expandAndCount(s, i, i + 1); } return count; } private int expandAndCount(String s, int left, int right) { int count = 0; while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { count++; left--; right++; } return count; } }

这个思路比动态规划写起来更简洁，也好理解。我第一次做 647 的时候用的动态规划，后来发现中心扩展写起来更不容易出错。所以我建议你把两种写法都掌握，面试时看情况选用。

3. 动态规划回文表：数个数与分割问题的通用底座

3.1 如何用动态规划判断任意子串是否回文

中心扩展法是“按需判断”，而动态规划的做法是“一次性预处理”。我们定义一个二维布尔数组dp[i][j]，表示子串s[i..j]是否为回文串。状态转移的核心逻辑是：

一个子串是回文串，必须满足两个条件：

1. 两端字符相等，即s.charAt(i) == s.charAt(j)；
2. 去掉两端之后，内部子串也是回文串，即dp[i+1][j-1]为true。

但这里有个边界细节：当子串长度小于等于 3 时，只要两端字符相等，内部子串即使只有一个字符或为空，也一定是回文。比如"aa"，两端相等，内部为空，当然是回文；"aba"，两端相等，内部b是回文。所以转移公式可以写成：

dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i+1][j-1])

这里j - i <= 2就包含长度 1、2、3 三种情况，非常优雅。

这个预处理过程如果能自己想明白，其实就是理解了动态规划里“大问题依赖小问题”的思想。你不需要真的去记忆公式，抓住“两端相等、内部回文”这个语义，随时能自己推出来。

3.2 遍历顺序：这是最容易写错的地方

dp[i][j]依赖的是dp[i+1][j-1]，也就是“左下角”的格子。如果你用常规的双层循环从i外层、j内层去填表，很可能会在计算时发现dp[i+1][j-1]还没被算出来。

我推荐的遍历方式是把右边界j放在外层，左边界i放在内层，并且保证i从 0 扫到j。这样在计算dp[i][j]时，任何dp[i+1][j-1]对应的右边界都是j-1，而j-1这个外层循环已经执行过了，所以这个值一定已经计算完成。

这个遍历顺序我开始也搞反过，后来把dp表打印出来才看明白。你调试时可以把表打出来对照，多看几遍之后就再也不会错了。

3.3 LeetCode 647 回文子串个数的动态规划 Java 实现

有了dp表，数回文子串个数的逻辑就很简单：枚举所有i <= j的区间，只要dp[i][j]为true就计数。完整代码如下：

class Solution { public int countSubstrings(String s) { int n = s.length(); if (n < 2) { return n; } boolean[][] dp = new boolean[n][n]; int count = 0; for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) { dp[i][j] = true; count++; } } } return count; } }

很多人会疑惑为什么dp表能数出正确个数。其实你只要想清楚一件事：dp[i][j]为true当且仅当s[i..j]是一个回文子串，那么把所有这样的区间数一遍，自然就是所有回文子串的数量。没有重复，也没有遗漏。

3.4 分割回文串：LeetCode 131 的回溯与 dp 表配合

LeetCode 131 要求返回所有可能的分割方案，使得每一段都是回文串。这是一个典型的“回溯 + 切割”问题，核心做法是：从左到右扫描，尝试每个可能的切割位置，如果当前这一段是回文，就递归处理剩余部分。

判断“当前这一段是否回文”如果每次都重新判断，会非常浪费。正确的做法是先用 3.1 中的dp表把回文信息全部算好，然后在回溯过程中直接用dp[start][end]判断。这样回溯的重点就放在“枚举所有切割方案”上，而不是反复做字符串字符比较。

完整 Java 代码如下：

class Solution { public List<List<String>> partition(String s) { List<List<String>> res = new ArrayList<>(); if (s == null || s.length() == 0) { return res; } int n = s.length(); boolean[][] dp = new boolean[n][n]; for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) { dp[i][j] = true; } } } backtrack(s, 0, dp, new ArrayList<>(), res); return res; } private void backtrack(String s, int start, boolean[][] dp, List<String> path, List<List<String>> res) { if (start == s.length()) { // 必须新建列表，否则 res 里的引用会被后续修改影响 res.add(new ArrayList<>(path)); return; } for (int end = start; end < s.length(); end++) { if (dp[start][end]) { path.add(s.substring(start, end + 1)); backtrack(s, end + 1, dp, path, res); // 回溯的关键：撤销刚才的选择 path.remove(path.size() - 1); } } } }

这里有一个新手很容易忽略的细节：res.add(new ArrayList<>(path))必须拷贝一份，而不是直接res.add(path)。因为path这个列表在后续回溯过程中还会被反复修改，如果直接加入res，最后所有结果都会变成同一个空列表或最后一个状态。这个错误我印象很深，因为我在刚开始刷回溯题时几乎每道题都踩一遍。

path.remove(path.size() - 1)是回溯的标准动作。你在添加一个子串、进入递归、返回之后，必须把这一层添加的内容移除，才能继续尝试下一个切割点。如果你漏了这一步，path会越积累越长，结果五花八门，而且非常难调试。

3.5 dp 表和回溯组合的复杂度思考

dp 预处理本身是 O(n^2) 的时间和 O(n^2) 的空间。回溯部分真正的耗时取决于有多少种分割方案。最坏情况下，比如字符串是"aaaa"，任意切割都是回文，方案数是 2^(n-1)，也就是指数级的，这在题目范围内是允许的，因为 LeetCode 131 要求返回所有方案，方案本身就有这么多。

面试官如果继续追问“只求最小切割次数”，那就是 LeetCode 132 的范畴，可以在 dp 回文表基础上再做一层一维 dp，复杂度降到 O(n^2)。不过我建议你先吃透 131 的回溯写法，再做 132 就顺理成章了。

4. 进阶武器：Manacher 算法为什么要学

4.1 中心扩展法的瓶颈在哪里

中心扩展法看起来已经不错了，但它最坏情况下是 O(n^2)。比如字符串是"aaaaaaaaaa"这种全相同字符，每个中心都要扩展到字符串边缘，大量的重复比较让人肉疼。有没有可能利用回文的对称性，把已经计算过的回文半径“复制”给后面的位置？这正是 Manacher 算法（马拉车算法）的核心思想。

我第一次看马拉车算法时觉得它很玄乎，后来拆开来看，发现它其实只做两件事：一是通过插入分隔符让所有回文串都变成奇数长度，二是维护一个“最右回文边界”和“中心”，利用对称性快速给当前位置一个初始半径。理解这两件事，算法就基本掌握了。

4.2 预处理：插入分隔符，把问题统一成奇数长度

在 Manacher 算法里，我们先把原始字符串每个字符的两边都插入一个不会出现在原串中的分隔符，比如#。例如"aba"变成"#a#b#a#"，"abba"变成"#a#b#b#a#"。

为什么要这么做？因为原始回文串有奇偶两种中心，插入分隔符后，无论原回文是奇数长度还是偶数长度，新串里的回文中心都落在字符上或#上，整个串的回文半径统一成奇数长度。这样代码只需要处理一种情况，不需要像中心扩展法那样分别调用两次。

还要注意原串和新串的下标换算。新串的下标i对应原串中的下标i / 2？不完全对，因为新串长度为2n+1。我们在实现时通常不直接依赖这个换算，而是最后通过中心下标和半径反推原串起点，这个后面细说。

4.3 算法核心：回文半径数组、中心 C 与右边界 R

定义数组p[i]表示新串中以第i个字符为中心，能扩展到的最远回文半径长度。注意这里“半径”指的是从中心向外扩展的步数，不算中心自己。例如新串"#a#b#a#"，中心b的下标是 3，p[3] = 3，表示左右各能扩展 3 步，覆盖整个"#a#b#a#"。

同时维护两个变量：

• C：当前已知最右回文子串的中心；
• R：当前已知最右回文子串的右边界，也就是C + p[C]。

当我们扫描到一个新位置i时，如果i < R，说明i在当前已知的最右回文串内部。根据回文对称性，i关于中心C的镜像位置mirror = 2 * C - i的回文半径p[mirror]可以部分复用。但由于镜像位置的半径可能越过R的边界，所以初始值只能取Math.min(R - i, p[mirror])。这句是马拉车算法最精华的一行，理解它，整个算法就通了。

举个例子，新串"#a#b#b#a#"，扫描到中心C右边某个位置时，如果镜像位置的回文半径已经完全包含在C的回文区间内，那么当前中心至少也有同样大的半径；如果镜像半径越过R，那就只能先保守地从R - i开始，再继续向外暴力扩展，因为R以外的信息还没被验证过。

4.4 最长回文子串的 Manacher Java 实现

下面是我自己整理的 Java 实现，已经把越界检查都处理好了。这个版本可以直接跑 LeetCode 5，也能扩展到求子串个数。

class Solution { public String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } // 1. 预处理：插入分隔符 StringBuilder sb = new StringBuilder("#"); for (char ch : s.toCharArray()) { sb.append(ch).append('#'); } String t = sb.toString(); int n = t.length(); int[] p = new int[n]; int C = 0; int R = 0; int maxLen = 0; int centerIndex = 0; for (int i = 0; i < n; i++) { // 2. 利用对称性初始化 p[i] if (i < R) { int mirror = 2 * C - i; p[i] = Math.min(R - i, p[mirror]); } // 3. 尝试继续向外扩展 int left = i - (p[i] + 1); int right = i + (p[i] + 1); while (left >= 0 && right < n && t.charAt(left) == t.charAt(right)) { p[i]++; left--; right++; } // 4. 更新最右边界 C 和 R if (i + p[i] > R) { R = i + p[i]; C = i; } // 5. 记录最长回文信息 if (p[i] > maxLen) { maxLen = p[i]; centerIndex = i; } } // 6. 由新串下标反推原串起点 int start = (centerIndex - maxLen) / 2; return s.substring(start, start + maxLen); } }

我在写第 3 步时有一个容易出错的地方：left和right的初始值是i - (p[i] + 1)和i + (p[i] + 1)，意思是先从已经确认的半径外一步开始试探。如果你写成i - p[i]，就会把中心字符自己也重复比较一次，导致半径偏大。调试时用"abba"这种例子一眼就能看出来。

最后一步的起点换算：新串中回文子串的起点是centerIndex - maxLen，因为maxLen就是回文半径（也是原串回文长度），中心左边半径那么多位置内的字符都是回文的一部分。而在插入了#之后，原串下标和新串下标的关系是原串下标 = 新串下标 / 2的整数部分？严谨地说是用这个公式。这里直接(centerIndex - maxLen) / 2就可以得到原串起点。我在本地跑过"babad"、"cbbd"、"aaaa"，结果都正确，你可以放心用。

4.5 马拉车算法的复杂度与适用范围

马拉车的时间复杂度是 O(n)，因为虽然每个位置都可能触发 while 扩展，但总的扩展次数是有限的：R这个右边界只增不减，整体最多向后移动 n 次。空间复杂度 O(n)。

不过我需要提醒一点：马拉车算法在面试时并不是必考项。大多数大厂的面试题，O(n^2) 的解法已经完全够用。如果你的目标是把 LeetCode 热门 100 题刷完，马拉车可以放到后面慢慢看，先把中心扩展和动态规划写熟练更重要。但如果你面的是对算法复杂度要求很高的团队，或者面试官明确追问“能不能做到 O(n)”，这时马拉车就是你展示实力的加分项。

我个人是把马拉车当作“专题里的最后一块拼图”来学的，学完之后再回头看中心扩展法，会明显感觉到思路上的升华：从“重复计算”到“利用对称性复用”，这种优化思想其实在 KMP、Next 数组里也很常见。

5. 刷题过程中的常见坑与面试心得

5.1 边界条件清单，强烈建议背下来

回文子串题出错，十有八九是边界条件。下面这张表是我反复踩坑之后整理出来的，每次写完代码我都会照着快速过一遍。

比如 LeetCode 5，输入"a"时如果你的代码没有做空串判断就直接substring，会抛StringIndexOutOfBoundsException；输入"ac"时，最长回文子串应该返回"a"或"c"都可以，但如果你没有把单字符中心纳入枚举，就会拿到空串。

5.2 Java 实现中的几个容易忽略的性能与语法细节

第一，substring在 Java 7 之后是拷贝字符数组的，时间复杂度 O(n)，不是 O(1)。如果在一个热循环里反复截取大量子串，会有不小的开销。在 LeetCode 131 这类回溯题里，为了生成结果必须调用substring，这是不可避免的；但在中心扩展求最长回文时，我建议不要每次更新都截一次，而是只记录起点和长度，最后截取一次。

第二，charAt和toCharArray的选择。在读多不写少的场景，两者差距不大。但如果你要在一个很长的字符串上频繁按索引取字符，比如马拉车算法的 while 循环，我个人习惯先转成char[]数组，访问arr[i]比反复调用s.charAt(i)稍快，而且代码写起来更简洁。你在力扣上能看到很多 Java 高手都是这么干的。

第三，boolean[][] dp的默认值是false，不需要手动初始化。但要注意，只有被你显式赋值true的位置才表示回文，没赋值的位置就是false。千万别写dp[i][j] = dp[i+1][j-1]这种式子，因为dp表示的是“是回文”，而不是“长度”或其他数值。

5.3 从回文子串延伸出去的变种题

回文子串的底层能力练熟之后，你会发现它像一座桥，能通向很多其他题目。我把自己做过的相关题按推荐顺序列出来，你可以当成一条延伸路线：

1. LeetCode 9 回文数：最简单，整型反转一半，注意溢出。
2. LeetCode 234 回文链表：快慢指针找中点，反转后半段，再比较。
3. LeetCode 680 验证回文串 II：双指针逼近，最多删一个字符时用贪心思路。
4. LeetCode 214 最短回文串：要用到 KMP 或马拉车，难度较高，建议后期挑战。
5. LeetCode 132 分割回文串 II：先做回文表，再做一维 dp 求最小切割次数。

这串题做下来，你对“子串类动态规划”和“对称性判断”的敏感度会明显提升。我自己是先刷完 5、647、131 这三个基础题，再去做 234 和 680，感觉过渡得很自然。面试时如果需要现场推公式，回文表这套思路能给足你底气。

5.4 一个小技巧：本地准备一个回文自测用例集

刷这类题时，我强烈建议你在本地main方法里准备一组固定用例，每次写完算法先跑一遍自测，再去力扣提交。我常用的测试集类似这样：

public static void main(String[] args) { Solution solution = new Solution(); String[] tests = {"", "a", "aa", "ab", "aaaa", "abac", "babad", "cbbd"}; for (String test : tests) { System.out.println("\"" + test + "\" -> " + solution.longestPalindrome(test)); } }

这组用例覆盖了空串、单字符、纯偶数回文、纯奇数回文、全部相同字符、混合场景。一个算法只要能跑过这八个输入，再去力扣提交基本不会出大问题。这个方法比反复在网页上试错快得多，尤其是马拉车这种公式多、起点换算容易错的算法，本地打印中间结果能帮你一眼定位问题。

最后再分享一个我这半年来反复验证过的体会：回文子串题的大部分解法，本质上都是在“预计算或者快速判断‘某个子串是否是回文’”。中心扩展是按需扩展，动态规划是按长度递推建表，马拉车是按对称性复用半径。把这一层想透，面试时任何回文变种你都能很快定位到该用哪把钥匙。我自己是在被 131 这道题的数组越界坑过一次，认真画出递归树之后才真正把这块吃透的。希望这份笔记能帮你少走点弯路。