LeetCode LCR 020. 回文子串

约 4 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 动态规划 LCR

题目描述

✅ LCR 020. 回文子串

image-20260928234927729

题意分析

统计字符串中有多少个连续子串是回文。每个子串按起止下标区分，即使内容完全相同，只要位置不同也要分别计数；允许这些子串互相重叠。

单个字符本身就是回文，所以每个位置都至少贡献一个结果。题目要的是全部回文子串的数量，不是最长回文的长度，也不是去重后的回文内容种类。

解法：中心扩展

核心思路

[!blue]

回文具有由内向外扩张的结构：如果内部已经对称，再向左右各加一个相同字符，得到的更长区间仍然回文。因此可以从各个中心出发，每成功扩张一层就计入一个新的回文子串，而不用为每个区间从头验证。

中心有两种。奇数长度回文以某个字符为中心，初始左右指针都在 center；偶数长度回文以相邻字符之间的空隙为中心，初始指针在 center 与 center + 1。共有 n 个字符中心和 n - 1 个有效空隙中心，二者都必须枚举。

对固定中心，只有左右边界有效且当前两端相等时才能增加计数，然后同时向外移动。遇到失配后必须停止：这对不相等字符会继续位于同一中心更大区间的对称位置，即使更外层相等，也无法修复内部的冲突。

每个回文区间都有唯一的中心和唯一的扩张层数，因此会在对应中心下恰好被统计一次。不同中心得到不同位置的区间，同一中心的不同层得到不同长度的区间，不需要额外去重。

代码对每个字符都调用奇数和偶数两种扩张。最后一个字符右侧的空隙已经越界，辅助函数会直接返回零；保留这个调用能让外层写法统一，同时不会漏掉最后一个单字符回文。

解题步骤

  1. 答案初始化为零，从左到右枚举每个字符下标作为 center。
  2. 从 (center, center) 开始扩张，统计奇数长度回文。
  3. 从 (center, center + 1) 开始扩张，统计偶数长度回文。
  4. 扩张中每成功比较一对边界字符就计数加一，再向两侧继续移动；越界或失配即停止。
  5. 累加所有中心的成功次数，返回总数。

代码实现

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;

        for (int center = 0; center < s.length(); center++) {
            ans += expand(s, center, center);
            ans += expand(s, center, center + 1);
        }

        return ans;
    }

    private int expand(String s, int left, int right) {
        int count = 0;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 每扩展成功一次，就对应一个新的回文子串。
            count++;
            left--;
            right++;
        }

        return count;
    }
}

func countSubstrings(s string) int {
    ans := 0
    for center := 0; center < len(s); center++ {
        ans += expandPalindrome(s, center, center)
        ans += expandPalindrome(s, center, center+1)
    }
    return ans
}

func expandPalindrome(s string, left int, right int) int {
    count := 0
    for left >= 0 && right < len(s) && s[left] == s[right] {
        // 奇偶中心都通过同一个扩展函数统计。
        count++
        left--
        right++
    }
    return count
}

复杂度分析

  • 时间复杂度：O(n²)。中心数量为 O(n)，每个中心最多向外扩张 O(n) 层；全部字符相同时达到平方量级。
  • 空间复杂度：O(1)。只使用左右下标、当前计数和总计数，不保存区间状态表。

关键点总结

[!green]

  • 按位置计数，重复内容无需去重。
  • 奇数中心是字符，偶数中心是空隙，两种情况一起覆盖全部回文。
  • 中心与扩张层数唯一确定区间，直接累加成功次数便不重不漏。
  • 失配后同中心的更长区间仍包含该冲突，必须停止扩张。

易错点总结

[!yellow]

  • 只枚举字符中心：会漏掉全部偶数长度回文。
  • 按字符串内容去重：同样内容在不同位置出现仍应分别统计。
  • 每个中心只计最长的一次：较短的每个成功扩张层也都是独立子串。
  • 失配后继续向外比较：更外层相等不能修复已经不对称的内部。
  • 先读字符后检查边界：扩张可能到达负下标或字符串末尾之外，应先通过边界判断。
  • 为了避免最后偶数中心越界而少枚举一个下标：会一起漏掉最后字符的奇数中心，越界应由辅助函数处理。

相似题目

题目 难度 关联与区别
5. 最长回文子串 中等 同样可中心扩展，原题保留最长区间，本题把每次成功扩展计为一个回文子串。
516. 最长回文子序列 中等 原题是可跳过字符的子序列，本题要求连续区间，状态与扩展方式不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/18287440
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！