647. 回文子串
647. 回文子串
题目链接（中等）
题目描述
给你一个字符串 s，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
数据范围：
1 <= s.length <= 1000s由小写英文字母组成
示例
示例 1：
输入： s = "abc"
输出： 3
解释： 三个回文子串："a"、"b"、"c"
示例 2：
输入： s = "aaa"
输出： 6
解释： 6 个回文子串："a"、"a"、"a"、"aa"、"aa"、"aaa"
核心思路
枚举所有回文子串，有三种常见思路：
- 中心拓展：枚举每个回文中心，向两边扩展，时间 $O(n^2)$，空间 $O(1)$；
- 动态规划：
dp[i][j]表示s[i..j]是否为回文，时间 $O(n^2)$，空间 $O(n^2)$； - Manacher：线性时间 $O(n)$，但实现较复杂。
中心拓展是最推荐的解法：思路直观，时间可接受，空间 $O(1)$。
方法一：中心拓展
思路及解法
核心观察：每个回文串都有一个「中心」。
- 若回文串长度为奇数（如
"aba"），中心是一个字符； - 若回文串长度为偶数（如
"abba"），中心是两个字符之间的间隙。
枚举所有可能的回文中心：长度为 n 的字符串共有 2n - 1 个回文中心：
n个单字符中心（奇数长度）；n - 1个间隙中心（偶数长度）。
统一枚举技巧：令 i 从 0 到 2n - 2，则：
i为偶数时，l == r，对应奇数长度回文；i为奇数时，r == l + 1，对应偶数长度回文。
以每个中心向两边扩展：若 s[l] == s[r]，则 s[l..r] 是回文，计数 +1，继续扩展 l -= 1, r += 1；否则停止。
举例：s = "abc"，n = 3，i 从 0 到 4：
i |
l |
r |
是否匹配 | 计数 |
|---|---|---|---|---|
| 0 | 0 | 0 | s[0]=='a' 自身 |
+1 |
| 1 | 0 | 1 | 'a' != 'b' |
— |
| 2 | 1 | 1 | s[1]=='b' 自身 |
+1 |
| 3 | 1 | 2 | 'b' != 'c' |
— |
| 4 | 2 | 2 | s[2]=='c' 自身 |
+1 |
总共 3 个，正确。
代码
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
ans = 0
for i in range(n):
# 奇数长度回文，中心为 i
l, r = i, i
while l >= 0 and r < n and s[l] == s[r]:
ans += 1
l -= 1
r += 1
# 偶数长度回文，中心为 i 和 i+1 之间
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
ans += 1
l -= 1
r += 1
return ans复杂度分析
- 时间复杂度：$O(n^2)$，共 $2n - 1$ 个中心，每个中心最多扩展 $O(n)$ 次。
- 空间复杂度：$O(1)$。
方法二：动态规划
思路及解法
定义 dp[i][j] 表示 s[i..j] 是否为回文子串。
转移方程：
遍历顺序：dp[i][j] 依赖 dp[i+1][j-1]，所以需要按长度从小到大或i 从大到小、j 从小到大遍历。
答案：统计所有 dp[i][j] == True 的数量。
代码
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = 0
# i 从后往前，j 从前往后
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
if j - i <= 1:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j]:
ans += 1
return ans复杂度分析
- 时间复杂度：$O(n^2)$，共 $n^2$ 个状态。
- 空间复杂度：$O(n^2)$，二维
dp数组。
方法三：Manacher 算法（线性时间）
思路及解法
Manacher 算法能在 $O(n)$ 时间内求出以每个位置为中心的最长回文半径。
预处理：在字符之间和两端插入 #，把奇偶回文统一成奇数长度。
例如 "abaa" → "#a#b#a#a#"。
核心思想：利用已经计算出的回文信息，避免重复扩展。
设：
f[i]：以i为中心的最大回文半径；iMax、rMax：当前已知的回文右端点最大的回文中心及右端点。
转移：
- 若
i <= rMax，利用对称点j = 2 * iMax - i：f[i] = min(f[j], rMax - i + 1)； - 若
i > rMax，f[i] = 1。
然后继续向两边扩展，并更新 iMax、rMax。
统计答案：原字符串中以 i 为中心的回文子串数量为 f[i] / 2（整除）。
注意：本题 $n \le 1000$，中心拓展完全够用，Manacher 主要作为进阶了解。
代码
class Solution:
def countSubstrings(self, s: str) -> int:
# 预处理：加 # 分隔符，两端加哨兵
t = "$#"
for c in s:
t += c + "#"
t += "!"
n = len(t)
f = [0] * n
i_max, r_max = 0, 0
ans = 0
for i in range(1, n - 1):
# 初始化 f[i]
if i <= r_max:
f[i] = min(r_max - i + 1, f[2 * i_max - i])
else:
f[i] = 1
# 中心拓展
while t[i + f[i]] == t[i - f[i]]:
f[i] += 1
# 更新 i_max, r_max
if i + f[i] - 1 > r_max:
i_max, r_max = i, i + f[i] - 1
# 统计答案
ans += f[i] // 2
return ans复杂度分析
- 时间复杂度：$O(n)$，每个位置最多扩展一次。
- 空间复杂度：$O(n)$，存储处理后的字符串和
f数组。
三种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 中心拓展 | $O(n^2)$ | $O(1)$ | 思路最直观，面试首选 |
| 动态规划 | $O(n^2)$ | $O(n^2)$ | 状态定义清晰，可扩展 |
| Manacher | $O(n)$ | $O(n)$ | 效率最高，但实现复杂 |
推荐：
- 面试：首选中心拓展，代码简短、思路清晰、空间 $O(1)$；
- 加分：能说出 Manacher 的思路，展示对字符串算法的深入理解。
关键细节
1. 为什么是 2n - 1 个中心
长度为 n 的字符串中：
n个字符位置可以作为奇数长度回文的中心；n - 1个字符间隙可以作为偶数长度回文的中心。
总共 n + (n - 1) = 2n - 1 个中心。
2. 统一中心的技巧
l = i // 2
r = l + i % 2i为偶数（i = 2k）：l = k, r = k（单字符中心）；i为奇数（i = 2k+1）：l = k, r = k+1（间隙中心）。
这样一次循环就能同时处理奇偶情况。
3. 动态规划遍历顺序
dp[i][j] 依赖 dp[i+1][j-1]，所以必须先算小区间再算大区间。
写代码时 i 从 n-1 递减到 0，j 从 i 递增到 n-1，保证 dp[i+1][j-1] 已经算好。
4. Manacher 的哨兵作用
在字符串两端加 $ 和 ! 这两个「不可能相等」的字符：
- 保证扩展时不会越界；
- 不需要额外的边界判断，代码更简洁。
5. Manacher 的答案统计
由于插入了 #，原字符串的回文子串数量为 f[i] / 2（向下取整），累加即可。
6. 与 LC 5（最长回文子串）的关系
- LC 5：求最长的回文子串；
- LC 647：求所有回文子串的数量。
两者都可以用中心拓展或 Manacher 求解，只是统计方式不同。
总结
- 核心问题：统计所有回文子串的数量；
- 中心拓展（推荐）：
- 枚举
2n - 1个回文中心； - 用
l = i // 2, r = l + i % 2统一奇偶； - 向两边扩展，统计匹配数量；
- 时间 $O(n^2)$、空间 $O(1)$；
- 枚举
- 动态规划：
dp[i][j]表示s[i..j]是否回文；- 按区间长度从小到大遍历；
- 时间 $O(n^2)$、空间 $O(n^2)$；
- Manacher：
- 插入
#统一奇偶； - 利用对称性加速，时间 $O(n)$；
- 本题规模小，作为进阶了解。
- 插入
相关题目
- LC 5. 最长回文子串（求最长而非计数）
- LC 516. 最长回文子序列（子序列，不要求连续）
- LC 9. 回文数（数字版）
- LC 125. 验证回文串（判断单个字符串是否回文）
- LC 132. 分割回文串 II（回文 + DP）