企业官网建设流程全解析

1. 问题拆解：Palindromic Substrings 究竟在考什么

LeetCode 0647 这道题，题面非常简单：给定一个字符串，需要返回这个字符串中所有回文子串的数量。注意是子串，不是子序列。子串要求连续，子序列只要求相对顺序一致，这两个概念前置条件完全不同，考法和解法也完全不同。

很多第一次刷到这道题的人，第一反应是暴力枚举所有子串，再逐个判断是不是回文。这个方法在小数据量下没问题，但字符串长度一旦到了 1000 以上，就直接超时。因为暴力枚举所有子串的时间复杂度是 O(n^2)，每个子串判断回文又要 O(n)，整体 O(n^3)，基本告别了通过测试的可能。

这道题真正的考察点有两个：一是你是否能发现回文的中心扩展特性，用 O(n^2) 时间、O(1) 空间解决；二是你是否掌握动态规划的经典表格推导思路，用 O(n^2) 时间、O(n^2) 空间解决。两种解法在面试中都是高频考法，前者更优，后者能体现表格推导的基本功，都值得吃透。

我在实际刷题时，第一次写的也是暴力解法，结果在长度几百的测试用例上就卡住了。后来重新审视题目，发现回文的判定天然适合“从中心向外扩散”的思路，才真正理解了这道题的本质。

先明确一下核心概念：回文串就是正着读和反着读一样的字符串，单字符天然是回文，空串通常不算。子串要求连续截取，比如 "abc" 的子串有 "a"、"b"、"c"、"ab"、"bc"、"abc" 六个。题目要求统计字符串中所有回文子串的数量，每个位置的单字符都会贡献一个计数。

这道题的输入范围通常到 1000 级别，也意味着任何 O(n^3) 方案都不可行，至少要到 O(n^2)。理解了这层约束，自然就能接受中心扩展和动态规划这两条主流路线。

2. 中心扩展法为什么是最优解

中心扩展法的核心思想很朴素：回文串是关于中心对称的，从中心向两边扩展，只要左右字符相等，就继续扩展，直到不相等为止。每一个回文子串都有一个“中心”，这个中心可以是一个字符，也可以是两个字符之间的空隙。

2.1 奇偶长度的统一处理技巧

回文串有两种形态：奇数长度如 "aba"、偶数长度如 "abba"。奇数长度回文的中心是单个字符，偶数长度回文的中心是双字符。如果分别枚举两种中心，需要在代码里写两次循环。更优雅的写法是统一处理：把每个字符当作奇数中心，把每个相邻字符对当作偶数中心。

以字符串 "abc" 为例：

• 奇数中心有 3 个：a、b、c
• 偶数中心有 2 个：ab 之间、bc 之间
• 总中心数是 2n - 1 = 5 个，正好对应所有可能回文子串的对称轴

这就是代码中常见的for i in range(n)加for j in [0, 1]两层循环的来历。j 等于 0 时处理奇数长度，j 等于 1 时处理偶数长度。这个技巧看着简单，但很多人第一次写时会把两个循环分开写，代码冗长且容易漏掉边界。

2.2 判定过程和计数逻辑

选定一个中心后，用两个指针 left 和 right 分别向左右扩展，初始位置取决于奇数还是偶数中心。奇数中心 left = right = i，偶数中心 left = i、right = i + 1。只要 left 大于等于 0 且 right 小于字符串长度，且 s[left] 等于 s[right]，就说明找到了一个新的回文子串，计数加一，然后 left 减一、right 加一。

举个例子，s = "aaa"，以 index 1 为奇数中心扩展：

• left = 1，right = 1，s[1] == s[1]，计数加 1，得到 "a"
• left = 0，right = 2，s[0] == s[2]，计数加 1，得到 "aaa"
• left = -1，超出边界，循环结束

这个中心一共贡献了 2 个回文子串。三个单字符中心各贡献 1 个，两个偶数中心在中点处左右字符相等各自贡献 1 个，总共 6 个，和 "aaa" 的全部子串都是回文的事实完全吻合。

2.3 Python 代码实现与复杂度分析

class Solution: def countSubstrings(self, s: str) -> int: n = len(s) ans = 0 for i in range(n): for j in [0, 1]: left = i right = i + j while left >= 0 and right < n and s[left] == s[right]: ans += 1 left -= 1 right += 1 return ans

这段代码非常精简，时间复杂度是 O(n^2)。最外层循环 n 次，内层每次从中心最多扩展 n 次，整体数量级是 n 乘以 n 再乘以常数 2，也就是 O(n^2)。空间复杂度 O(1)，只用了几个变量，没有任何额外存储。

这里的外层循环 i 代表的是中心位置而非子串起点，这点非常关键。如果把 i 理解成子串起点，代码逻辑就会完全走偏。我在初学阶段踩过这个坑，当时把 while 循环里的扩展逻辑和 i 的语义搞混，导致输出结果大量偏少。

注意：中心扩展法不需要单独处理回文串长度大于等于 2 的情况，因为每次成功扩展都必然对应一个新回文子串。奇数中心从单字符开始扩展，偶数中心从双字符开始扩展，天然覆盖了所有可能长度，不会漏解也不会重复计数。

2.4 中心扩展与暴力枚举的对比

暴力枚举需要三层循环，第一层定起点，第二层定终点，第三层判断回文。中心扩展法则是两层循环，外层定中心，内层扩展并判断。从思维模型来看，暴力枚举是“枚举所有区间再验证”，中心扩展是“利用回文对称性直接生成回文”。相当于暴力枚举先画好所有可能线段再检查是否对称，而中心扩展直接以对称轴为起点向两边生长，少了大量无效计算。

实测里，同样一个长字符串，暴力解法在数百字符时就明显卡顿，中心扩展法在上千字符时依然毫秒级返回。这也是这道题在面试中经常被追问“能否优化”的原因，从暴力到中心扩展的思维跃迁，就是考官想看到的优化意识。

3. 动态规划解法的表格推演

动态规划解法虽然时空复杂度不如中心扩展，但它的思路在更多字符串类题目中有复用价值，比如最长回文子串、分割回文串等。把这类题目的状态转移逻辑吃透，再去做其他变体题会轻松很多。

3.1 dp 数组定义与状态转移方程

定义 dp[i][j] 表示字符串从下标 i 到下标 j 的子串是否为回文，true 表示是，false 表示不是。当 s[i] 等于 s[j] 时，子串能否构成回文取决于中间部分 s[i+1:j] 是否回文，因此状态转移方程是：

• dp[i][j] = dp[i+1][j-1]，当 j - i >= 2 且 s[i] == s[j]
• dp[i][j] = true，当 j - i == 1 且 s[i] == s[j]
• dp[i][j] = true，当 i == j

注意没有判断 s[i] == s[j] 时，dp[i][j] 一定为 false，因为首尾字符不等则整个子串不可能回文。

这个递推关系非常符合直觉：判断一段字符串是否回文，可以剥离首尾字符后看内部子串。范围渐渐缩小，最终落到单字符或者双字符这种基础情况，基础情况可以直接给出结果。这就是动态规划的底柱思维，大问题拆成小问题，小问题答案已知后反推大问题。

3.2 为什么遍历顺序是长度从小到大的关键

这是动态规划解法里最容易出错的地方。很多初学者把 dp 二维数组所有格子按从左到右、从上到下遍历，结果发现计算 dp[i][j] 时 dp[i+1][j-1] 还没被算出来，拿到的是默认值 false，答案全错。

原因在于子串按长度分组：一个长回文的判定依赖更短回文的判定。必须先算长度为 1 的子串，再算长度为 2 的，依此类推。所以外层循环应该枚举子串长度，内层循环枚举子串起点，保证每次计算时内部子串的长度已经处理完成。

按长度递增的顺序推演一个例子，s = "abba"：

• 长度为 1：dp[0][0]、dp[1][1]、dp[2][2]、dp[3][3] 全部为 true，回文数 4
• 长度为 2：dp[0][1] = false，dp[1][2] = false，dp[2][3] = false，因为相邻字符都不相等
• 长度为 3：dp[0][2]，s[0]=a、s[2]=b 不相等，false；dp[1][3]，s[1]=b、s[3]=a 不相等，false
• 长度为 4：dp[0][3]，s[0]=a、s[3]=a 相等，依赖 dp[1][2] = false，所以整体 false

最终回文数就是 dp 数组中 true 的个数，结果为 4，只有四个单字符。注意 "bb" 是回文，但在长度为 2 的遍历中 dp[1][2] 对应的是 "bb"，s[1]=b、s[2]=b 相等，因此这里判断条件里要写 j - i == 1 时直接 true，我上面推导时写的是 false，容易误导，需要重新梳理。

重新严谨推演 "abba"：

• 长度为 1：四个单字符均 true，回文数 4
• 长度为 2：子串 "ab" false，"bb" true，"ba" false，回文数加 1，累计 5
• 长度为 3：子串 "abb"，s[0]=a、s[2]=b 不等，false；"bba"，s[1]=b、s[3]=a 不等，false
• 长度为 4：子串 "abba"，s[0]=a、s[3]=a 相等，依赖 dp[1][2]，也就是 "bb"，为 true，整体 true，回文数加 1，累计 6

最终结果是 6，回文子串分别是 "a"、"b"、"b"、"a"、"bb"、"abba"。这个推演过程建议在草稿纸上画一个二维表格，把每次计算填入对应格子，能非常直观地看出 dp[i][j] 依赖的是左下角 dp[i+1][j-1]。

3.3 Python 代码实现与内存优化

class Solution: def countSubstrings(self, s: str) -> int: n = len(s) dp = [[False] * n for _ in range(n)] ans = 0 for length in range(1, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] == s[j]: if length <= 2: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j]: ans += 1 return ans

这里有两个细节值得注意。第一，length <= 2直接置 true，省去了对 dp[i+1][j-1] 的越界判断。第二，统计 true 数量直接放在判断之后，不需要单独再遍历 dp 数组。

复杂度方面，时间 O(n^2)，空间 O(n^2)，因为需要一个二维布尔表来记录所有子串的回文状态。对于 n 等于 1000 的输入，这个内存开销大约是 100 万个布尔值，Python 里实际占用的内存不低，但依然能通过。如果追求更极致，可以把二维数组压缩成滚动一维数组，因为当前长度只依赖上一个长度的结果，但这会让代码可读性下降，面试时建议先写二维版本保证正确性。

3.4 动态规划与中心扩展的选择建议

实际做题或面试时，我的建议是优先写中心扩展法，因为空间开销小、代码短、边界条件少。但理解动态规划版本也很重要，面试官问起 “还有别的解法吗”，能流畅写出 DP 版本会加分。而且这道题的 DP 思路迁移到最长回文子串问题时，只需要同步记录最大长度和起点即可，几乎零成本复用。

4. 常见错误与排障心得

4.1 暴力枚举三层循环的复杂度陷阱

这件事我刷题初期反复栽跟头。每次看到回文题，下意识就是三层循环：枚举 i、枚举 j、判断子串。等提交后看到超时红色提示，才意识到复杂度问题。后来养成了一个习惯，审题时先看数据范围，如果 n 在 1000 以上，O(n^3) 的方案直接可以放弃。这道题 n 的上限就是 1000 左右，暴力解法在中间几个测试用例就会被卡住，没必要浪费时间提交。

4.2 动态规划遍历方向写错

我见过不止一个人把 DP 版本写成直接按 i 从 0 到 n、j 从 0 到 n 的双层循环，结果输出完全错误。因为这个方向下，计算 dp[i][j] 时依赖的 dp[i+1][j-1] 根本没有先算出来。判断逻辑也特殊：i 代表起点，j 代表终点，j 通常不小于 i，所以只看矩阵右上三角即可。很多新手会把左下三角也初始化或遍历，非但没有帮助，反而在统计 true 数量时不必要地重复计数。

判断遍历方向是否正确，最简单的方法是把状态转移方程写出来，看看依赖的目标格子是在当前格子的哪个方向。比如 dp[i][j] 依赖 dp[i+1][j-1]，在当前格子的左下角，所以遍历顺序必须保证左下角先被计算。因此按长度递增枚举最安全，每次 i 和 j 的跨度一致，永远满足依赖条件。

4.3 中心扩展时奇偶中心遗漏

如果用两个独立循环分别处理奇偶中心，偶尔会漏掉所有偶数长度回文或者奇数长度回文。特别是字符串长度较短、偶数回文出现在端点位置时，比如 "aa" 开头的字符串，只枚举单字符中心就会漏掉整体 "aa" 这个偶数回文。统一处理的技巧是循环for center in range(2 * n - 1)，left 用 center // 2，right 用 center // 2 + center % 2。这种方式能把所有中心一网打尽，代码也不容易遗漏。

4.4 Python 边界判断的简写技巧

在 while 循环里连续写三个条件很容易看花眼，尤其是 left 和 right 的边界判断。我的习惯是先把 left 和 right 的边界条件写在循环条件最前面，防止索引越界后再比较字符，因为 Python 里索引为负不会立刻报错，比如 s[-1] 是最后一个字符，这会导致回文判定完全失真。具体而言，当 left 扩展成 -1 时，s[left] 会取到字符串末尾字符，可能意外地等于 s[right]，造成多余的计数。这属于 Python 特有的坑，不熟悉的语言细节可能会让排查非常痛苦。

4.5 测试用例选择的经验

验证代码正确性时，我不建议一上来就跑大用例，而是先用小规模但边界丰富的用例手工推演。

• 空字符串：返回 0
• 单字符字符串："a"，返回 1
• 全相同字符："aaa"，返回 6
• 交替字符："abab"，逐项数也能验证
• 包含偶数回文的经典串："abba"
• 随机生成长度为 50 左右的字符串，用暴力解法对拍结果

用暴力解法对拍是一个非常实用的技巧，小数据的暴力结果能快速验证优化解法的正确性。我刷题时经常把暴力版本和优化版本同时跑随机数据，一旦结果不一致就调试。这个小习惯帮我抓出过不少隐藏 bug。

4.6 面试中的展开与延伸

这道题还有一个进阶话题：Manacher 算法，可以在 O(n) 时间内求出最长回文子串以及回文子串数量。面试时如果时间充裕，可以提一嘴这个算法存在，但通常不建议为了这道题硬写 Manacher，因为代码复杂度较高，面试中容易写岔。能熟练写出中心扩展法并解释清楚动态规划递推关系，这道题已经算答得很好了。我在自己准备面试时，对这道题的要求就是两个解法都能手写，且能说清各自的时间和空间复杂度，以及为什么动态规划必须按长度遍历。

5. 两种解法的模板化总结与刷题建议

回文类题目在 LeetCode 上是一个大家族，有最长回文子串、回文子串数量、分割回文串、回文链表等一堆变体。这道题之所以值得反复刷，是因为它的两个解法分别代表了回文题的两条基本路线：中心扩展是几何直觉，动态规划是状态递推。

建议刷题顺序如下：先做最长回文子串，体会中心扩展如何同时维护最大长度；再做这道回文子串数量题，体会如何统计全部数量；最后做分割回文串，在回文判定的基础上增加回溯切割。

在写代码时，我还有个经验：不要追求一上来就写出最精简的版本，而是先把逻辑完整写清楚，正确通过后再优化代码结构。比如中心扩展法可以先写两个独立循环，一个处理奇数、一个处理偶数，验证通过后再合并成统一版本。这样能显著降低首次编码的心理负担，也方便调试定位问题。

这道题在真实面试中出现频率很高，属于必须熟练掌握的基础题。掌握两种解法并能清楚解释复杂度和遍历顺序后，再做其他回文题基本都能举一反三。

我个人在反复刷这道题的过程中，最大的体会是审题时分析复杂度边界比闷头写代码重要得多。想清楚数据范围决定了哪些方案可行，这个习惯帮我在很多题目上避免了无效尝试。另外，在草稿纸上把 DP 表格画出来再编码，比直接敲代码更能理解状态依赖关系，这个做法也推荐给大家。