题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

样例

输入："abc"
输出：3
解释：三个回文子串："a"，"b"，"c"。

输入："aaa"
输出：6
解释：6个回文子串："a"，"a"，"a"，"aa"，"aa"，"aaa"。

注意

• 输入的字符串长度不会超过 1000。

算法

(暴力枚举) $O(n^2)$

1. 每次固定回文子串的中间位置，然后向左右开始扩展。
2. 每次固定后，分为奇数长度和偶数长度两种情况，然后暴力统计答案。

时间复杂度

• 每次共有 $O(n)$ 个中间位置，固定后，最坏情况下需要 $O(n)$ 的时间扩展回文串，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0;
                 i - j >= 0 && i + j < n && s[i - j] == s[i + j];
                 j++)

                ans++;

            for (int j = 1; 
                 i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j];
                 j++)

                ans++;
        }
        return ans;
    }
};