回文子串 图解题解

回文子串这题在数什么

给字符串 s，统计其中回文子串的总个数。两条规则决定了计数口径：子串必须连续；只要起止位置不同就算不同的子串，哪怕内容一模一样。比如 "aa" 里两个 "a" 要算两个。s = "abacaba" 的答案是 12——单字符 7 个，再加 "aba"（两处）、"aca"、"bacab"、"abacaba"。

为什么不逐个子串验证回文

暴力路线是枚举全部 O(n²) 个子串、每个花 O(n) 验证，总共 O(n³)。真正的浪费在于验证之间零复用："bacab" 从两端往里比，比到一半其实撞上了 "aca" 已经回文的事实，却当作不知道重比一遍。

把视角从「子串」换到「中心」就能复用这份信息：任何回文都关于自己的中心对称。固定一个中心向外扩，里层对称成立时只需再比最外侧两个字符，就能判定大一圈的子串是不是回文——里层的结论被直接继承，每往外一层只花 O(1)。

为什么每扩一层计数就加一

中心扩展和计数能严丝合缝地咬合，靠的是一个对应关系：以某中心向外扩张，第一层对称成功对应以它为中心的最短回文，再扩一层成功就对应大一圈的另一个回文。也就是说「对称成功一次」和「一个回文子串」一一对应，所以 while 循环里每比中一次就 ans 加一。

不重不漏也由中心保证：每个回文子串的中心是唯一确定的（奇数长度中心在字符上，偶数长度中心在缝隙上），它只会在枚举到自己中心时被数到一次，不同位置的相同内容因为中心不同而分别计数，正合题意。

2n-1 个中心怎么用一层循环枚举

中心必须包含 n 个字符和 n-1 条缝隙，共 2n-1 个——漏掉缝隙中心，所有偶数长度的回文（如 "bb"）就永远数不到。参考代码用一个循环变量 c 从 0 走到 2n-2 统一编码两类中心：l = c // 2，r = c // 2 + c % 2。c 为偶数时 l 与 r 重合，是字符中心；c 为奇数时 r 比 l 大一，正好落在缝隙两侧。这样一层循环替代了奇偶两套代码。

复杂度多少，还有什么别的解法

中心 2n-1 个，每个最多向外扩约 n/2 层，时间 O(n²)；只用两个指针和一个计数器，空间 O(1)。写扩展循环时越界判断要放在字符比较之前——while 条件先查 l >= 0 且 r < n，顺序反了会越界访问。

同类解法还有区间动态规划：dp[i][j] 表示 s[i..j] 是否回文，由 s[i] == s[j] 且 dp[i+1][j-1] 推出，时间同为 O(n²) 但要 O(n²) 空间。追求线性时间可用 Manacher 马拉车算法，靠对称性复用回文半径做到 O(n)，实现复杂，通常面试点到为止。

Python

def countSubstrings(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 ans

C++

int countSubstrings(string s) {
    int n = s.size(), 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++;
            l--; r++;
        }
    }
    return ans;
}

Java

public int countSubstrings(String s) {
    int n = s.length(), 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++;
            l--; r++;
        }
    }
    return ans;
}