647. 回文子串(动态规划)

 

难度中等679

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

示例 1：

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

示例 2：

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

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        // dp[i][j] :s[i:j] 表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
        int cnt = 0;
        for(int i = n-1; i>=0;i--) {
            for(int j = i; j < n;j++) {
                // 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
                if (s[i]==s[j]) {
                    //情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
                    if (i==j) dp[i][j] = true; 
                    // 情况二：下标i 与 j相差为1，例如aa，也是文子串
                    else if(j-i==1) dp[i][j] = true;
                    // 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j   区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
                    else {
                        if (dp[i+1][j-1]) dp[i][j] = true;   
                    }
                }
                if(dp[i][j]) cnt++;
            }
        }
        return cnt;
    }
};

双指针、中心扩散

class Solution {
public:
    int find(string& s, int low, int high) {
        int cnt = 0;
        while(low>=0 && high <s.size()  && s[low]==s[high]) {
            cnt++;
            low--;
            high++;
        }
        return cnt;
    }
    int countSubstrings(string s) {
        int n = s.size();
        int res = 0;
        for(int i = 0;i < n;++i) {
            res+=find(s,i,i);
            res+=find(s,i,i+1);
        }
        return res;
    }
};