企业官网建设流程全解析

回文子串这个专题，我前前后后刷过三轮。第一轮上来就直接做最长回文子串，结果被动态规划的状态转移卡到怀疑人生；第二轮换了个顺序，从统计回文子串数量那道基础题入手，才真正体会到中心扩展的妙处；第三轮又从源码层面把 Manacher 过了一遍，算是把整个专题彻底吃透了。这篇文章就是把这几轮的笔记整理成一份 Java 视角的学习路线，适合正在准备面试、刚开始刷 LeetCode 但又被回文类题目搞晕的同学，也适合已经会做几道题、想系统梳理一遍思路的人。

先说结论：回文子串的核心问题就两种——"统计有多少个回文子串"和"找出最长回文子串"。围绕这两个问题，中心扩展、动态规划、Manacher 是三条最经典的路线。我建议的掌握顺序是：中心扩展优先，动态规划跟上，Manacher 作为进阶理解。下面按照这个顺序把每个思路的代码、推导和坑都过一遍。

1. 回文子串题群的共同骨架：判定、计数、最长，三条主线

1.1 从"验证回文"到"枚举子串"的思维转变

回文串的定义很简单：正着读和倒着读一样，比如"aba"、"abba"。判断一个串是不是回文，双指针从两端往中间走就行，这是所有回文题的地基。

但一旦题目变成"这个字符串里有多少个回文子串"或者"最长的回文子串是多长"，问题就复杂了。难点在于：你需要知道的不再是"整串是不是回文"，而是"所有子串里哪些是回文"。如果直接枚举所有子串再逐个检查，复杂度是 O(n³)，n 稍微到几百就明显吃力。

所以这个专题真正要解决的核心问题只有一个：如何高效地枚举并判断子串是否为回文。

从这个问题出发，自然衍生出两个方向：

• 以每个字符或相邻字符间隙为中心，向两边扩展——这是中心扩展法；
• 用dp[i][j]记录子串s[i..j]是否是回文——这是动态规划法；
• 利用回文的对称性，复用之前计算过的回文半径——这是 Manacher 算法。

这三条主线其实不是竞争关系，而是递进关系。理解它们的共同骨架，刷题时就不会觉得每道题都是新题。

1.2 三类主流解法的定位与复杂度对比

这里有个经验之谈：如果面试中不特别说明数据范围，给一个 O(n²) 的中心扩展完全够用，而且它空间 O(1)，代码又短，是面试时最不容易出错的方案。Manacher 更多是作为"你知不知道还有更优解"的加分项，后面我会专门讲。

2. 中心扩展法：最推荐优先掌握的解法

2.1 为什么枚举"中心"不会重复也不会漏

中心扩展法有个天然的数学优势：任意一个回文子串，都有且只有一个对称中心。

奇数长度的回文子串，中心是某个真实字符，比如"aba"的中心是'b'；偶数长度的回文子串，中心是两个相邻字符之间的"空隙"，比如"abba"的中心在'b'和'b'之间。

所以对于一个长度为 n 的字符串，可能的中心一共有 2n-1 个：n 个字符中心，加上 n-1 个空隙中心。枚举每一个中心，从半径 0 开始向左右扩展，每次扩展成功就产生一个新的回文子串。因为每个子串的中心唯一，不同中心扩展出来的结果不可能重复；又因为所有中心都被枚举到了，所以也不可能漏掉任何一个回文子串。

这个"不重不漏"的性质，是所有回文子串计数题能放心使用中心扩展的根本保证。

2.2 统计回文子串数量的完整 Java 实现

以 LeetCode 的"回文子串"计数题为例，完整代码如下：

public int countSubstrings(String s) { int n = s.length(); int ans = 0; for (int i = 0; i < n; i++) { ans += expand(s, i, i); // 奇数长度中心 ans += expand(s, i, i + 1); // 偶数长度中心 } return ans; } private int expand(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; }

这里的expand返回的是以当前中心能扩展出多少个回文子串，而不是最长扩展距离。因为每向外扩一步成功，就代表一个新的回文子串诞生。例如s = "aba"，以i = 1（字符'b'）为中心时，expand("aba", 1, 1)会先数出"b"，再数出"aba"，返回 2。

我自己最多犯的一个错误是忘记奇数中心和偶数中心要分开调用。expand(s, i, i)处理单字符中心，expand(s, i, i + 1)处理双字符间隙中心，两个都不能少，否则像"aa"、"abba"这种偶数长度回文就全漏了。

2.3 常见误区：中心扩展不是"一个中心只管一条线"

有人会把中心扩展写成这样：

// 错误示范：只向左或只向右扩展，或者不同步 while (left >= 0 && s.charAt(left) == s.charAt(right)) { left--; right++; }

看起来没错，但少了right < length的边界判断，在偶数中心i + 1越界时会抛异常。更常见的问题是想当然地认为"每个中心只要扩一次就行"，忽略了while要持续扩展到边界为止。

还有同学会把中心扩展和双指针验证回文搞混。验证回文是"左右两端往中间夹"，中心扩展是"中间往左右两边扩散"，方向完全不同。刷题时如果切不过来，建议在代码注释里写清楚：这是以中心向外的扩展，不是双指针向内的逼近。

2.4 从计数到求最长：同一个模板的简单变形

理解了计数，求最长回文子串就是顺手的事。还是枚举 2n-1 个中心，只不过expand不再计数，而是返回能扩展的最长半径长度，然后维护全局最大值和起始下标：

public String longestPalindrome(String s) { int n = s.length(); if (n < 2) return s; int start = 0, maxLen = 1; for (int i = 0; i < n; i++) { int len1 = expandLen(s, i, i); int len2 = expandLen(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 expandLen(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }

注意这里expandLen返回的是right - left - 1，因为最后跳出循环时左右指针都多走了一步。以s = "aba"为例，中心i = 1：从左=1、右=1 开始，第一次匹配后 left=0、right=2，第二次匹配后 left=-1、right=3，循环结束，right - left - 1 = 3 - (-1) - 1 = 3，正好是"aba"的长度。

起始下标start = i - (len - 1) / 2这个公式，奇数偶数都适用。比如"abba"的偶数中心i = 1、i + 1 = 2，扩展出长度为 4 的回文，start = 1 - (4 - 1) / 2 = 0，正确。

3. 动态规划版本：布尔表的填充顺序是硬约束

3.1 状态定义与转移方程的由来

中心扩展虽然好用，但面试官经常会追问一句："能不能用动态规划做？" 这时候你需要能熟练写出第二种方案。

定义状态dp[i][j]表示s[i..j]这一段子串是否为回文。它是一个布尔值，true 表示回文。转移方程如下：

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

这个方程的逻辑很直观：如果首尾字符相等，并且去掉首尾后的内部子串也是回文，那么整个子串就是回文。关键在于j - i <= 2这个条件，它覆盖了三种不需要查内部状态的短串：

• 长度为 1：i == j，单字符天然回文；
• 长度为 2：如"aa"，首尾相等即回文；
• 长度为 3：如"aba"，首尾相等，中间只剩一个字符，一定回文。

如果不加j - i <= 2，长度为 2 时会去访问dp[i+1][j-1]，此时左边界大于右边界，在二维表里是无效位置；长度为 3 时会访问dp[i+1][i+1]，虽然合法，但会让逻辑变得绕。所以这道题的题解普遍建议用j - i <= 2 || dp[i+1][j-1]的写法。

3.2 外层循环为什么必须是"右边界"或"长度"

这是 DP 写法里最大的坑。因为dp[i][j]依赖dp[i+1][j-1]，也就是说，要计算某个状态，必须保证左边界加 1、右边界减 1 的那个状态已经被算过。

正确的遍历方式有两种：

方式一：外层遍历右边界 j。

public int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int ans = 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; ans++; } } } return ans; }

方式二：外层遍历子串长度。

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

很多初学者第一次写，会直觉地写成"外层 i 从 0 到 n，内层 j 从 i 到 n"。这种写法算dp[i][j]时，dp[i+1][j-1]对应的行i+1还没开始遍历，永远是 false，于是所有长度大于 3 的回文子串全部漏判。我在早期刷题时就在这个坑里蹲了很久，最终的解决办法就是背下"外层 j 递增，内层 i 从 0 到 j"这个顺序，同时心里默念：右边的先算，左下角的依赖自然就有。

3.3 一维滚动数组的写法与雷区

二维布尔表有 O(n²) 空间，n 到 5000 时差不多 2500 万个 boolean，Java 里 boolean 数组实际按 1 字节算，也要 25 MB 左右，能接受但不算优雅。用一维滚动数组可以把空间压到 O(n)。

思路是：外层 j 递增时，只需要保留上一轮j-1的结果。关键代码：

public int countSubstrings(String s) { int n = s.length(); boolean[] dp = new boolean[n]; int ans = 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])) { dp[i] = true; ans++; } else { dp[i] = false; } } } return ans; }

注意这里内层 i 是从 0 到 j 正向遍历的。为什么？因为计算dp[i]时需要的dp[i+1]必须还是上一轮j-1的结果，而正向遍历时i+1还没被当前轮更新，所以取到的是旧值，正好是二维写法里的dp[i+1][j-1]。

如果内层循环写成从j到0反向遍历，计算dp[i]时dp[i+1]已经被当前轮更新过了，取到的就变成了dp[i+1][j]，语义完全错掉，结果会多算或漏算回文子串。这是我实测踩过的坑，印象很深。

4. Manacher 算法：理解对称臂之后，面试讲深不吃亏

4.1 为什么要学一个"看起来用不上"的线性算法

先说结论：绝大多数 LeetCode 题目的字符串长度不超过 1000 或 2000，O(n²) 的解法提交完全没有问题。但数据规模一旦到 10⁵，比如某些竞赛题，O(n²) 就会超时，Manacher 是线性 O(n) 的解法。

面试中直接要求手写 Manacher 的岗位不算多，但面试官可能会问一句："最长回文子串有没有 O(n) 的解法？" 这时你哪怕讲不清细节，也要能说出核心思想：插入分隔符统一奇偶长度，利用回文的对称性复用之前计算过的回文半径。

4.2 预处理串与臂长数组的含义

Manacher 第一步是把原串s变成一个新串，在每两个相邻字符之间插入#，并在开头加^、结尾加$两个不相同的哨兵字符。比如"aba"变成：

^ # a # b # a # $

为什么要插入#？因为原串的偶数长度回文没有"中心字符"，不好处理。插入后所有回文都变成以某个字符为中心，统一成奇数长度。哨兵^和$的作用是让扩展循环在到达边界时自然停止，不用显式判断越界。

定义数组p[i]表示新串中以 i 为中心向两边扩展的臂长。比如上面的新串中，中心是下标 4 的'b'，它能扩展出"#a#b#a#"，臂长 p[4] = 3，而原串的"aba"长度正好也是 3。在这个算法里，p[i]的最大值就是原串最长回文子串的长度。

4.3 利用对称性省掉重复比较

这是 Manacher 最核心的一步。维护两个变量：center是当前已知最右回文的中心，right是它能到达的最右边界。当我们遍历到某个位置 i 时，如果 i 在right之内，就一定能在当前已处理的回文段里找到它的对称位置mirror = 2 * center - i。

由于回文对称性，mirror位置的臂长p[mirror]可以"借"给 i。但要注意一个问题：mirror的臂长信息可能超出当前right的范围限制，所以 i 的初始臂长不能超过right - i：

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

取完初始值后，再继续向两边扩展比较t.charAt(i + p[i] + 1)和t.charAt(i - p[i] - 1)，直到字符不相等。这就是为什么这个算法线性：每个位置的臂长只扩展有限次，right本身是单调右移的，总的字符比较次数是 O(n) 级别。

4.4 Java 完整实现与验证用例

public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; StringBuilder sb = new StringBuilder("^"); for (char c : s.toCharArray()) { sb.append('#').append(c); } sb.append("#$"); String t = sb.toString(); int n = t.length(); int[] p = new int[n]; int center = 0, right = 0; int maxLen = 0, maxStart = 0; for (int i = 1; i < n - 1; i++) { int mirror = 2 * center - i; if (i < right) { p[i] = Math.min(right - i, p[mirror]); } while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) { p[i]++; } if (i + p[i] > right) { center = i; right = i + p[i]; } if (p[i] > maxLen) { maxLen = p[i]; maxStart = (i - maxLen) / 2; } } return s.substring(maxStart, maxStart + maxLen); }

我建议手写几遍这个实现，重点体会两个地方：一是p[i] = Math.min(right - i, p[mirror])这一行"借用但不越界"的取值逻辑；二是最后maxStart = (i - maxLen) / 2的换算，它把新串下标映射回原串下标。

验证一下："aba"预处理后中心'b'的下标为 4，p[4] = 3，maxStart = (4 - 3) / 2 = 0，返回"aba"。"abba"预处理后中心是中间插入的'#'，下标为 5，可以推出 p[5] = 4，maxStart = (5 - 4) / 2 = 0，返回"abba"。两个用例都能对上。

5. 变式题与边界条件：回文专题里最容易踩的坑

5.1 "删除一个字符后能否成为回文"的双指针思路

这个变式题很经典，条件从"是不是回文"变成"最多删一个字符后能不能是回文"。暴力做法是枚举删除哪个字符，复杂度 O(n²)，最优做法还是双指针。

先正常从两端向中间找第一对不匹配的位置l和r。此时有两种补救方式：删掉s[l]，继续验证[l+1, r]是否回文；或者删掉s[r]，继续验证[l, r-1]是否回文。只要两条路径有一条成功，就返回 true。

public boolean validPalindrome(String s) { int left = 0, right = s.length() - 1; while (left < right && s.charAt(left) == s.charAt(right)) { left++; right--; } if (left >= right) return true; return isRangePalindrome(s, left + 1, right) || isRangePalindrome(s, left, right - 1); } private boolean isRangePalindrome(String s, int left, int right) { while (left < right) { if (s.charAt(left) != s.charAt(right)) return false; left++; right--; } return true; }

这个解法的核心是：遇到第一个不匹配点时，把"删左"和"删右"两种情况都试一次，而不是继续在原来的双指针循环里纠结。我第一次写的时候犯过错误，只尝试删左边或只删右边，导致"abca"这类用例死活过不了。

5.2 输出所有回文子串时的裁剪开销

如果题目从"计数"变成"输出所有回文子串列表"，中心扩展依然适用，只需要在扩展成功时把s.substring(left, right + 1)加入结果：

private void expandCollect(String s, int left, int right, List<String> res) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { res.add(s.substring(left, right + 1)); left--; right++; } }

这里有个容易忽略的性能细节：Java 的substring在较新版本里是 O(len) 的字符串复制操作。回文子串数量本身可能达到 O(n²)，如果每个子串长度又很可观，总复制开销就变成 O(n³)。所以只用计数时，中心扩展是 O(n²)；一旦要求输出全部子串，复杂度会上涨，这是题目本身的性质决定的，不是算法不够好。如果题目还要求去重，放心，因为每个回文子串中心唯一，中心扩展天然不会重复，不需要额外 Set。

5.3 回文"子串"和回文"子序列"是两个不同的 DP

很多同学刷完回文子串，又去做"最长回文子序列"题目，发现中心扩展完全套不上，这是正常的。子串要求连续，子序列只要求字符顺序一致，不需要连续。

子序列 DP 的状态转移是：

s[i] == s[j] 时：dp[i][j] = dp[i + 1][j - 1] + 2 s[i] != s[j] 时：dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])

这个 DP 不是布尔表，而是长度表，逻辑完全不同。建议把这两类题分开整理，不要混在一个模板里记，否则做题时很容易把"连续"这个隐含条件丢掉。

5.4 边界用例清单

不管用哪种解法，提交前先跑一遍下面的用例：

尤其是"aaaa"，计数应为 4 + 3 + 2 + 1 = 10。我每次写完回文子串计数题，都会先拿这个用例跑一遍，它能同时暴露中心扩展漏偶数和 DP 填表方向错误的问题。

6. 复盘：我按什么顺序刷完回文专题

6.1 第一阶段：先用中心扩展把模板写到肌肉记忆

我的建议是把"统计回文子串数量"这道题作为专题入口，因为它代码最短、思路最直观，适合用来建立信心。第一天就把中心扩展模板抄三遍以上，直到不需要思考就能写出expand函数，并且能主动回答"为什么奇数偶数的中心都要枚举"。

第二天再去做"最长回文子串"，你会发现只是把返回值从计数改成长度，再把起始下标换算出来。同一个模板打两题，印象会非常牢固。

6.2 第二阶段：动态规划跟着"填表顺序"反复练

DP 部分不用贪多，关键是吃透那一个转移方程和两个遍历写法。我会在纸上画一个 5×5 的表格，把"abcba"手工填一遍，标出哪些格子先填、哪些后填，观察依赖方向。只有亲眼看到dp[i][j]依赖dp[i+1][j-1]，才会真正理解为什么外层不能按左边界 i 枚举。

6.3 第三阶段：Manacher 只求"讲得清、写得对"

Manacher 我没有要求自己背，而是分三步走：第一步只看代码和注释，搞清楚center、right、mirror三个变量分别代表什么；第二步自己画一个长一点的例子，手动模拟"abacaba"的整个遍历流程；第三步合上书，凭理解重新实现一遍，遇到卡壳的地方再对照原实现。

面试时如果被问到最长回文子串，我一般这样组织回答：先说暴力解 O(n³)，再说中心扩展 O(n²)，然后主动提一句"如果 n 很大，还有 Manacher 的 O(n) 解法，核心是利用回文对称性复用半径"。这样既有梯度，又能展示你对这个专题的理解深度。

最后再分享一个小习惯：我每次写回文相关题目，都会先在心里默念三件事——中心扩展要区分奇偶中心、DP 填表外层按右边界或长度、substring类操作注意复制开销。把这三个点记死，回文子串这个专题的绝大多数坑就都绕开了。