837. Palindromic Substrings

Code(Language:C++)

class Solution {
public:
    /**
     * @param str: s string
     * @return: return an integer, denote the number of the palindromic substrings
     */
    int countPalindromicSubstrings(string &str) {
        // write your code here
        //解放思想。用DP[i][j]表示起始第i和结尾第j个元素是否pali。
        // transfer: if(str[i - 1] == str[j - 1] && DP[i + 1][j-1]) DP[i][j] = true; 
        //initial: dp[i][i] = true; 
        const int n = str.size();
        if(n == 0){
            return 0; 
        }
        std::vector<vector<bool>> DP(n + 1, vector<bool>(n + 1, false));
        for(int i = 0; i <= n; i++){
            DP[i][i] = true; 
        }
        int res = 0; 
        for(int i = n; i >= 1; i--){
            for(int j = i; j <= n; j++){
                if(j == i + 1){
                    DP[i][j] = (str[i - 1] == str[j - 1]); 
                }
                else if (j > i + 1){
                    DP[i][j] = (str[i - 1] == str[j - 1]) && DP[i + 1][j - 1]; 
                }
                if(DP[i][j]){
                    res++; 
                }
            }
        }
        return res; 
        
    }
};