647. Palindromic Substrings

O(n) manacher’s algorithm不会
brute force O(n²) time O(1) space
跟5. Longest Palindromic Substring一样，直接数数即可

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += helper(s, i, i);
            cnt += helper(s, i, i + 1);
        }
        return cnt;
    }

    int helper(const string &s, int l, int r) {
        int cnt = 0;
        for (int n = size(s); l >= 0 && r < n && s[l] == s[r]; ++cnt, --l, ++r);
        return cnt;
    }
};

划分型dp O(n²) time O(n²) space
isPalin[i][j] = s[i] == s[j] && isPalin[i + 1][j - 1]
f[i][j] = f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1] + isPalin[i][j]

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n));
        vector<vector<bool>> isPalin(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
            isPalin[i][i] = true;
        }
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
            f[i][i + 1] = 2 + isPalin[i][i + 1];
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                isPalin[i][j] = (s[i] == s[j] && isPalin[i + 1][j - 1]);
                f[i][j] = f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1] + isPalin[i][j];
            }
        }
        return f[0][n - 1];
    }
};

其实没有必要维护一个计数的矩阵，直接用一个cnt就可以了

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<bool>> isPalin(n, vector<bool>(n));
        for (int i = 0; i < n; ++i) {
            isPalin[i][i] = true;
        }
        int cnt = n;
        for (int i = 0; i < n - 1; ++i) {
            isPalin[i][i + 1] = (s[i] == s[i + 1]);
            cnt += isPalin[i][i + 1];
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                isPalin[i][j] = (s[i] == s[j] && isPalin[i + 1][j - 1]);
                cnt += isPalin[i][j];
            }
        }
        return cnt;
    }
};