题目描述

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

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


示例 1：

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

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

提示：

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

算法1

(暴力枚举)

1 以每个字母为中心 每次左右向外扩展+1 查看字母是否相等。
如果相等则是回文 如果不是则不必继续检测，因为已经出现不对称，不可能出现回文了
2 以i i+1字母为中心 每次左右向外扩展+1 查看字母是否相等。
如果相等则是回文 如果不是则不必继续检测，因为已经出现不对称，不可能出现回文了

参考文献

C++ 代码

class Solution {
public:

    bool Check(const string& s, int l, int r)
{
    if (s[l] == s[r]) return true;


    return false;
}

int countSubstrings(string s) {
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        int l = i; int r = i;
        while (l >= 0 && r < s.size()) {
            if (Check(s, l, r)) ans++;
            else break;
            l--; r++;
        }
    }

    for (int i = 0; i < s.size(); i++) {
        int l = i; int r = i+1;
        while (l >= 0 && r < s.size()) {
            if (Check(s, l, r)) ans++;
            else break;
            l--; r++;
        }
    }


    return ans;
}

};

----------

算法2

动态规划 dp[i][j] 表示 字符串索引i到j是否是回文字符串

C++ 代码

class Solution {
public:
    vector<vector<int>> dp;
    int countSubstrings(string s) {
        int n = s.size()+10;
        dp = vector<vector<int>> (n,vector<int>(n));

        for(int i = 0; i < s.size();i++){
            dp[i][i] = 1;
        }

        for(int j = 0;j<s.size();j++){
            for(int i = j;i>=0;i--){
                if(s[i]== s[j] && j-i<=1) dp[i][j] =1;
                if(s[i] == s[j] && j-i >1 && dp[i+1][j-1] == 1){
                    dp[i][j] =1;
                }
            }
        }
        int count = 0;
        for(int i = 0; i <s.size();i++){
            for(int j = 0; j < s.size();j++){
                if(dp[i][j]==1) count++;
            }
        }

        return count;
    }
};