题目描述：
给你一个字符串
s，请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。
示例 1：
输入：s = "abc"输出：3解释：三个回文子串: "a", "b", "c"示例 2：
输入：s = "aaa"输出：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
解题思路：
方法一：中心扩展法（最优）
核心思路：
回文串一定有一个中心：
奇数长度：中心是一个字符（如
"aba"中心是b）偶数长度：中心是两个字符之间（如
"abba"中心是bb之间）
从每个中心向两边扩展，每扩展成功一次，回文子串数量 +1。
具体过程示例：
s = "aaa"
中心 i=0 ('a'): 扩展 → "a" ✅ 中心 i=1 ('a'): 扩展 → "a" ✅, "aaa" ✅ 中心 i=2 ('a'): 扩展 → "a" ✅ 偶数中心: 中心 i=0.5: 扩展 → "aa" ✅ 中心 i=1.5: 扩展 → "aa" ✅ 总共: 3 + 2 + 1 = 6 ✅代码实现：
class Solution { public: int countSubstrings(string s) { int count = 0; for (int i = 0; i < s.size(); i++) { // 奇数长度回文，中心是 s[i] count += expandAroundCenter(s, i, i); // 偶数长度回文，中心是 s[i] 和 s[i+1] 之间 count += expandAroundCenter(s, i, i + 1); } return count; } private: int expandAroundCenter(string& s, int left, int right) { int count = 0; while (left >= 0 && right < s.size() && s[left] == s[right]) { count++; left--; right++; } return count; } };复杂度分析：
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 每个中心扩展 O(n)，共 n 个中心 |
| 空间复杂度 | O(1) | 只用常数个变量 |
方法二：动态规划
核心思路：
状态定义：
dp[i][j]=s[i..j]是否是回文子串。
状态转移：
如果 s[i] == s[j]: 如果 j - i <= 1: dp[i][j] = true（单个或两个字符） 否则: dp[i][j] = dp[i+1][j-1]
代码实现：
class Solution { public: int countSubstrings(string s) { int n = s.size(); vector<vector<bool>> dp(n, vector<bool>(n, false)); int count = 0; // 按长度递增遍历 for (int len = 1; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s[i] == s[j]) { if (len <= 2 || dp[i+1][j-1]) { dp[i][j] = true; count++; } } } } return count; } };复杂度分析：
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 双重循环 |
| 空间复杂度 | O(n²) | dp 数组 |
方法三：Manacher 算法（O(n)）
核心思路：
和 LeetCode 5 题「最长回文子串」的 Manacher 算法一样，但统计的是所有回文子串的数量。
每个中心的回文半径p[i]表示以i为中心的回文半径，这个中心贡献的回文子串数量是(p[i] + 1) / 2。
代码实现：
class Solution { public: int countSubstrings(string s) { // 预处理 string t = "^#"; for (char c : s) { t += c; t += '#'; } t += '$'; int n = t.size(); vector<int> p(n, 0); int center = 0, right = 0; int count = 0; for (int i = 1; i < n - 1; i++) { if (i < right) { p[i] = min(right - i, p[2 * center - i]); } while (t[i + p[i] + 1] == t[i - p[i] - 1]) { p[i]++; } if (i + p[i] > right) { center = i; right = i + p[i]; } count += (p[i] + 1) / 2; } return count; } };复杂度分析：
| 维度 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 线性 |
| 空间复杂度 | O(n) | p 数组 |
三种方法对比：
| 方法 | 时间复杂度 | 空间复杂度 | 代码复杂度 | 推荐度 |
|---|---|---|---|---|
| 中心扩展 | O(n²) | O(1) | 简单 | ⭐⭐⭐⭐⭐ |
| 动态规划 | O(n²) | O(n²) | 中等 | ⭐⭐⭐⭐ |
| Manacher | O(n) | O(n) | 复杂 | ⭐⭐⭐ |
中心扩展是面试首选：代码简洁，空间 O(1)。
关键细节：
1. 为什么中心扩展要处理奇偶两种情况？
奇数回文：
"aba"，中心是单个字符偶数回文：
"abba"，中心是两个字符之间
所以需要对每个位置调用两次扩展：expand(i, i)和expand(i, i+1)。
2. 为什么每扩展成功一次就count++？
因为每扩展成功一次，就发现了一个新的回文子串。
3. 动态规划的遍历顺序
必须按长度递增遍历，因为dp[i][j]依赖dp[i+1][j-1]（更短的子串）。
4. 和「最长回文子串」的区别
| 题目 | 区别 |
|---|---|
| 5. 最长回文子串 | 求最长的那一个 |
| 647. 回文子串 | 统计所有回文子串的个数 |
总结：
| 要点 | 说明 |
|---|---|
| 核心思想 | 从每个中心向两边扩展，统计回文个数 |
| 关键操作 | 奇数中心(i,i)，偶数中心(i,i+1) |
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(1) |
