Medium

题目描述

给定一个字符串 s，返回其中回文子串的数目。

如果字符串正读和反读都相同，那么它是回文串。

子串是字符串中连续的字符序列。

示例 1：

输入: s = "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c"。

示例 2：

输入: s = "aaa"
输出: 6
解释: 六个回文子串: "a", "a", "a", "aa", "aa", "aaa"。

约束条件：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

提示：

  • 如何重用之前计算的回文来计算更大的回文？
  • 如果 “aba” 是回文，那么 “xabax” 是回文吗？类似地，“xabay” 是回文吗？
  • 复杂度提示：如果我们使用暴力法检查每个起始和结束位置的子串是否为回文，我们有 O(n²) 个起始-结束对和 O(n) 回文检查。我们可以通过重用之前的计算将回文检查时间减少到 O(1) 吗？

解题思路

这道题有三种主要解法：

方法一：中心扩展法（推荐）

从每个可能的回文中心开始，向两边扩展。回文中心可能是单个字符（奇数长度回文）或两个相邻字符之间（偶数长度回文）。对于每个中心，不断向外扩展，直到不满足回文条件为止。

方法二：动态规划

使用二维 dp 数组，其中 dp[i][j] 表示从索引 i 到 j 的子串是否为回文。状态转移方程为：

  • 如果 s[i] == s[j] 且 dp[i+1][j-1] 为真，则 dp[i][j] 为真
  • 特殊情况：长度为 1 或 2 的子串需要单独处理

方法三：Manacher算法

专门用于解决回文问题的线性时间算法，但实现较复杂。

推荐使用中心扩展法，因为它思路清晰、代码简洁，时间复杂度为 O(n²)，对于题目的数据规模完全够用。

代码实现

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        int count = 0;
        
        // 遍历每个可能的回文中心
        for (int i = 0; i < n; i++) {
            // 奇数长度回文，以 i 为中心
            count += expandAroundCenter(s, i, i);
            // 偶数长度回文，以 i 和 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.length() && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
};

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        
        def expand_around_center(left: int, right: int) -> int:
            cnt = 0
            while left >= 0 and right < n and s[left] == s[right]:
                cnt += 1
                left -= 1
                right += 1
            return cnt
        
        # 遍历每个可能的回文中心
        for i in range(n):
            # 奇数长度回文，以 i 为中心
            count += expand_around_center(i, i)
            # 偶数长度回文，以 i 和 i+1 为中心
            count += expand_around_center(i, i + 1)
        
        return count

public class Solution {
    public int CountSubstrings(string s) {
        int n = s.Length;
        int count = 0;
        
        // 遍历每个可能的回文中心
        for (int i = 0; i < n; i++) {
            // 奇数长度回文，以 i 为中心
            count += ExpandAroundCenter(s, i, i);
            // 偶数长度回文，以 i 和 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.Length && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

var countSubstrings = function(s) {
    const n = s.length;
    let count = 0;
    
    const expandAroundCenter = (left, right) => {
        let cnt = 0;
        while (left >= 0 && right < n && s[left]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度中心扩展法动态规划
时间复杂度O(n²)O(n²)
空间复杂度O(1)O(n²)

说明：

  • 中心扩展法：对于每个中心位置（共2n-1个），最多扩展n次，总体时间复杂度为O(n²)，只使用常数额外空间
  • 动态规划：需要填充n×n的二维表，时间和空间复杂度都是O(n²)

相关题目