647. Palindromic Substrings

647. Palindromic Substrings

自下而上，从单个字母和相邻两个字母相同的条件出发

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int ret{ 0 };
        for(int i = 0; i < n; ++i)
            ret += helper(s, n, i, i) + helper(s, n, i, i + 1); // 奇数的情况，从单个字母向外开展 偶数的情况，从相邻2个向外开展
        return ret;
    }
private:
    int helper(string& s, int n, int i, int j)
    {
        int ret{ 0 };
        while(i >= 0 && j < n && s[i--] == s[j++])
            ++ret;
        return ret;
    }
};

dp

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int ret = s.size();
        for(int i = 0; i < s.size(); ++i)
            dp[i][i] = true; // 单个字母的base
        for(int i = 0; i < s.size() - 1; ++i)
        {
            // 这里不能dp[i+1][i]，因为判断时候总是i<j，所以得保持顺序
            dp[i][i + 1] = s[i] == s[i + 1]; // 相邻两个字母相同的base
            ret += dp[i][i + 1] ? 1 : 0;
        }
        // 注意，由于每次的dp是基于长度缩小的区间，所以需要根据长度大小来遍历，从较短的长度遍历到较长的长度。
        for(int len = 3; len <= s.size(); ++len)
        {
            for(int i = 0, j = i + len - 1; j < s.size(); ++i, ++j)
            {
                dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
                ret += dp[i][j] ? 1 : 0;
            }
        }
        return ret;
    }
};

dpReview

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = 0; i < n; ++i)
            dp[i][i] = true;
        int ret = n;
        for(int i = 0; i < n - 1; ++i)
            if(dp[i][i + 1] = s[i] == s[i + 1])
                ++ret;
        for(int i = n - 1; i >= 0; --i)
            for(int j = i + 2; j < n; ++j)
                if(dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1])
                    ++ret;
        return ret;
    }
};