647. 回文子串
题目描述
输入一个字符串 s。
子串是 s 中一段连续的字符。若一个子串从左往右读和从右往左读完全一样，就称它为回文子串。
统计 s 中回文子串的个数并返回。起始位置或结束位置不同的子串分别计数，即使内容一样。
示例 1
输入：s = "abc" 输出：3
解释：只有三个单字符 "a"、"b"、"c" 是回文。
示例 2
输入：s = "aaa" 输出：6
解释：三个 "a"、两个 "aa" 和一个 "aaa"，共 6 个。
数据范围
1 <= s.length <= 1000s只包含小写英文字母。
解题思路：中心扩展
中心扩展。每个回文串都有唯一的中心：奇数长度的中心是一个字符，偶数长度的中心在两个字符之间，共 2n - 1 个中心。编号 c 对应 l = c // 2，r = l + c % 2。从中心向两侧扩展，只要 s[l] == s[r] 就多一个回文串，继续向外；一旦不等，更外层也不可能是回文，停止。
为什么正确
在同一个中心内，每次进入循环体时 s[l..r] 都是回文。
复杂度分析
时间 O(n^2)，空间 O(1)。
易错点
只枚举奇数长度的中心会漏掉 "aa" 这类偶数回文。也可以用 dp[i][j] = s[i]==s[j] and dp[i+1][j-1]，但需要 O(n^2) 空间。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
ans = 0
for c in range(2 * n - 1):
l, r = c // 2, c // 2 + c % 2
while l >= 0 and r < n and s[l] == s[r]:
ans += 1
l -= 1
r += 1
return ansclass Solution {
public int countSubstrings(String s) {
int n = s.length();
int ans = 0;
for (int c = 0; c < 2 * n - 1; c++) {
int l = c / 2, r = c / 2 + c % 2;
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
ans += 1;
l -= 1;
r += 1;
}
}
return ans;
}
}class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
int ans = 0;
for (int c = 0; c < 2 * n - 1; c++) {
int l = c / 2, r = c / 2 + c % 2;
while (l >= 0 && r < n && s[l] == s[r]) {
ans += 1;
l -= 1;
r += 1;
}
}
return ans;
}
};func countSubstrings(s string) int {
n := len(s)
ans := 0
for c := 0; c < 2*n-1; c++ {
l, r := c/2, c/2+c%2
for l >= 0 && r < n && s[l] == s[r] {
ans += 1
l -= 1
r += 1
}
}
return ans
}var countSubstrings = function(s) {
const n = s.length;
let ans = 0;
for (let c = 0; c < 2 * n - 1; c++) {
let l = c >> 1, r = (c >> 1) + (c % 2);
while (l >= 0 && r < n && s[l] === s[r]) {
ans += 1;
l -= 1;
r += 1;
}
}
return ans;
};function countSubstrings(s: string): number {
const n = s.length;
let ans = 0;
for (let c = 0; c < 2 * n - 1; c++) {
let l = c >> 1, r = (c >> 1) + (c % 2);
while (l >= 0 && r < n && s[l] === s[r]) {
ans += 1;
l -= 1;
r += 1;
}
}
return ans;
}其他解法
区间 DP 和中心扩展都是 O(n²)，前者用表记住每个区间，后者只需常数空间；Manacher 在中心扩展上复用对称信息，降到 O(n)。
解法 2：区间动态规划 时间 O(n²)，空间 O(n²)
dp[i][j] 表示 s[i..j] 是否为回文。s[i] == s[j] 且区间长度不超过 3，或者 s[i] == s[j] 且 dp[i + 1][j − 1] 为真时，dp[i][j] 为真。i 从大到小枚举，j 从 i 往右枚举，保证用到的内层区间已算好。每遇到一个真值就计数加一。
状态定义清楚，是区间 DP 的入门例题。时间与中心扩展相同，但要 O(n²) 空间。
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i < 3 or dp[i + 1][j - 1]):
dp[i][j] = True
ans += 1
return ansclass Solution {
public int countSubstrings(String s) {
int n = s.length(), ans = 0;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
}class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), ans = 0;
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
};func countSubstrings(s string) int {
n, ans := len(s), 0
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] && (j-i < 3 || dp[i+1][j-1]) {
dp[i][j] = true
ans++
}
}
}
return ans
}var countSubstrings = function(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(false));
let ans = 0;
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
};function countSubstrings(s: string): number {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(false));
let ans = 0;
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}解法 3：Manacher 算法 时间 O(n)，空间 O(n)
在字符之间插入 #，把奇偶两种回文统一成奇数长度。f[i] 记录以 i 为中心的最大回文半径。维护已知回文中右端点最远的一个（中心 iMax、右端 rMax）。i 在 rMax 内时，先用关于 iMax 的对称点的半径作初值，再向外扩展。原串中以该位置为中心的回文个数是 f[i] / 2（向下取整）。
利用回文的对称性复用已知结果，右端点只增不减，总时间线性。实现细节多，面试中较少要求。
class Solution:
def countSubstrings(self, s: str) -> int:
t = '$#' + '#'.join(s) + '#!'
m = len(t)
f = [0] * m
iMax, rMax = 0, 0
ans = 0
for i in range(1, m - 1):
f[i] = min(rMax - i + 1, f[2 * iMax - i]) if i <= rMax else 1
while t[i + f[i]] == t[i - f[i]]:
f[i] += 1
if i + f[i] - 1 > rMax:
iMax, rMax = i, i + f[i] - 1
ans += f[i] // 2
return ansclass Solution {
public int countSubstrings(String s) {
StringBuilder sb = new StringBuilder("$#");
for (char c : s.toCharArray()) sb.append(c).append('#');
sb.append('!');
String t = sb.toString();
int m = t.length(), iMax = 0, rMax = 0, ans = 0;
int[] f = new int[m];
for (int i = 1; i < m - 1; i++) {
f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
while (t.charAt(i + f[i]) == t.charAt(i - f[i])) f[i]++;
if (i + f[i] - 1 > rMax) {
iMax = i;
rMax = i + f[i] - 1;
}
ans += f[i] / 2;
}
return ans;
}
}class Solution {
public:
int countSubstrings(string s) {
string t = "$#";
for (char c : s) {
t += c;
t += '#';
}
t += '!';
int m = t.size(), iMax = 0, rMax = 0, ans = 0;
vector<int> f(m, 0);
for (int i = 1; i < m - 1; i++) {
f[i] = i <= rMax ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
while (t[i + f[i]] == t[i - f[i]]) f[i]++;
if (i + f[i] - 1 > rMax) {
iMax = i;
rMax = i + f[i] - 1;
}
ans += f[i] / 2;
}
return ans;
}
};func countSubstrings(s string) int {
t := []byte{'$', '#'}
for i := 0; i < len(s); i++ {
t = append(t, s[i], '#')
}
t = append(t, '!')
m := len(t)
f := make([]int, m)
iMax, rMax, ans := 0, 0, 0
for i := 1; i < m-1; i++ {
if i <= rMax {
f[i] = min(rMax-i+1, f[2*iMax-i])
} else {
f[i] = 1
}
for t[i+f[i]] == t[i-f[i]] {
f[i]++
}
if i+f[i]-1 > rMax {
iMax, rMax = i, i+f[i]-1
}
ans += f[i] / 2
}
return ans
}var countSubstrings = function(s) {
const t = '$#' + s.split('').join('#') + '#!';
const m = t.length;
const f = new Array(m).fill(0);
let iMax = 0, rMax = 0, ans = 0;
for (let i = 1; i < m - 1; i++) {
f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
while (t[i + f[i]] === t[i - f[i]]) f[i]++;
if (i + f[i] - 1 > rMax) {
iMax = i;
rMax = i + f[i] - 1;
}
ans += Math.floor(f[i] / 2);
}
return ans;
};function countSubstrings(s: string): number {
const t = '$#' + s.split('').join('#') + '#!';
const m = t.length;
const f = new Array(m).fill(0);
let iMax = 0, rMax = 0, ans = 0;
for (let i = 1; i < m - 1; i++) {
f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
while (t[i + f[i]] === t[i - f[i]]) f[i]++;
if (i + f[i] - 1 > rMax) {
iMax = i;
rMax = i + f[i] - 1;
}
ans += Math.floor(f[i] / 2);
}
return ans;
}