Problem647. 回文子串

思路：没啥思路，只会暴力，dp没想到

ACcode

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        int len = s.length();
        for(int i=1;i<=len;i++){
            for(int j = 0;j<len;j++){
                if(j+i-1<len){
                    bool flag = false;
                    for(int l=j,r=i+j-1;l<=r;l++,r--){
                        if(s[l]!=s[r]){
                            flag = true;
                            break;
                        }
                    }
                    if(!flag) ans++;
                }
            }
        }
        return ans;
    }
};

时间复杂度：$o(n^3)$奇怪的是居然能过！

在上面代码的基础上还可以优化掉第三层循环做到$o(1)$时间复杂度判断是否回文

思路：dp[i][j]表示s的[i:j]区间是否回文，这样扩展的时候只有三种情况：一个字符，两个字符，三个以上字符，就这三类，第三类可以有递推，dp[i][j]=dp[i-1][j-1]&&(s[i]==s[j])
代码：

class Solution {
public:
    int countSubstrings(string s) {
        int ans = 0;
        int len = s.length();
        vector<vector<int>> dp(len + 1, vector<int>(len + 1, 0));
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < len - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
            }
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < len; j++) {
                if (j + i - 1 < len) {
                    if (i == 1)
                        ans++;
                    else if (i == 2) {
                        if (dp[j][j + i - 1]) {
                            ans++;
                        }
                    } 
                    else {
                        if (dp[j + 1][j + i - 2] == 1 && s[j] == s[j + i - 1]) {
                            dp[j][j + i - 1] = 1;
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
};