天池 在线编程 回文子串（区间动态规划）

1 ≤ |s| ≤ 5000
Each character s[i] ∈ ascii[a-z]

示例
样例1:
输入: 
str = "abaaa"
输出:  
5
说明:
5个回文子串
a
aa
aaa
aba
b

样例2:
输入: 
str = "geek"
输出:  
4
说明:
4个回文子串
e
ee
g
k

class Solution {
public:
    /**
     * @param s: the string
     * @return: the number of substring
     */
    int countSubstrings(string &s) {
        // Write your code here.
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        set<char> set(s.begin(),s.end()); // 单个字符的子串
        unordered_set<string> oset;
        dp[0][0]=1;
        for(int i = 1; i < n; ++i)
        {
            dp[i][i] = 1; // 单个字符肯定是回文串
            if(s[i-1] == s[i])
            {
                dp[i-1][i] = 1;
                oset.insert(s.substr(i-1,2));
            }

        }
        
        for(int len = 2; len <= n; ++len)
        {
            for(int i = 0; i+len < n; ++i)
            {
                if(dp[i+1][i+len-1] && s[i] == s[i+len])
                {
                    dp[i][i+len] = 1;
                    oset.insert(s.substr(i,len+1));
                }
            }
        }
        return set.size() + oset.size();
    }
};

class Solution {
public:
    /**
     * @param str: s string
     * @return: return an integer, denote the number of the palindromic substrings
     */
    int countPalindromicSubstrings(string &s) {
        // write your code here
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        int ans = n;
        dp[0][0]=1;
        for(int i = 1; i < n; ++i)
        {
            dp[i][i] = 1;
            if(s[i-1] == s[i])
            {
                dp[i-1][i] = 1;
                ans++;
            }

        }
        
        for(int len = 2; len <= n; ++len)
        {
            for(int i = 0; i+len < n; ++i)
            {
                if(dp[i+1][i+len-1] && s[i] == s[i+len])
                {
                    dp[i][i+len] = 1;
                    ans++;
                }
            }
        }
        return ans;
    }
};