题目描述

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

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

样例

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

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

算法1

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

C++ 代码

class Solution {
public:
    bool judge(const string& s, int l, int r){
        while(l<=r){
            if(s[l]!=s[r])return false;
            l++;
            r--;
        }
        return true;
    }
    int countSubstrings(string s) {
        if(s.empty())return 0;
        int count=0;
        for(int i=0;i<s.size();i++)
            for(int j=i;j<s.size();j++)
                if(judge(s,i,j))count++;
        return count;
    }
};

算法2

(动态规划) $O(N^2)$

状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
dp[i][j]=(s[i]==s[j]&&(j-i<=2||dp[i+1][j-1]))

时间复杂度

$O(N^2)$

C++ 代码

class Solution {
public:
    int countSubstrings(string s) {
        if(s.empty())return 0;
        int sz=s.size(), count=0;
        vector<vector<int>> dp(sz, vector<int>(sz));
        for(int i=0;i<sz;i++){
            for(int j=0;j<=i;j++){
                dp[j][i]=(s[i]==s[j]&&(i-j<2||dp[j+1][i-1]));
                count+=dp[j][i];
            }
        }
        return count;
    }
};

算法3

(中心扩展) $O(N^2)$

奇数偶数中心扩展

时间复杂度

$O(N^2)$

C++ 代码

class Solution {
public:
    int countSubstrings(string s) {
        if(s.empty())return 0;
        int sz=s.size(), count=0;
        for(int i=0;i<sz;i++){
            int l=i, r=i;
            //奇数扩展
            while(l>=0&&r<sz&&s[l]==s[r])count++, l--, r++;
            //偶数扩展
            l=i, r=i+1;
            while(l>=0&&r<sz&&s[l]==s[r])count++, l--, r++;
        }
        return count;
    }
};