LeetCode 题解
    647. Palindromic Substrings 回文子字符串

    647. Palindromic Substrings 回文子字符串

    第一次解法

    从 DP 的角度考虑，因为需要所有所有的子串，因此需要一个二维数组来存放结果，dp[i][j] 表示下标 i - j 的字符串是回文串，如果 i == j ，则计数器+1，并标记 dp[i][j]为1，如果 i 到 j 的长度为 2，那么只要 s[i]==s[j]，就是回文串，如果长度大于2，就向左右进行扩散，新的左右字符相等且原有的串为回文，那么新串也为回文

    int countSubstrings(string s) {
    int len=s.size();
    int res=0;
    vector<vector<bool> > dp(s.size(), vector<bool>(s.size(), false));
	// 长度为 1
    for(int i=0;i<len;++i) {
        ++res;
        dp[i][i]=true;
    }
	// 长度为 2
    for(int i=1;i<len;++i) {
        if(s[i]==s[i-1]) {
            ++res;
            dp[i-1][i]=true;
        }
    }
	// 长度为 3 ~ N
    for(int i=len-3;i>=0;--i) {
        for(int j=i+2;j<len;++j) {
            if (s[i]==s[j] && dp[i+1][j-1]) {
                ++res;
                dp[i][j]=true;
            }
        }
    }
    return res;
}

    第二种解法：直接扩散法

    回文串的对称中心可以是字符串中任意一个字符或者是两个相邻字符

    int countSubstrings(string s) {
    int res=0;
    for(int i=0;i<s.size();++i) {
        countPalin(s, i, i, res);	// 回文串长度为奇数
        countPalin(s, i, i+1, res);	// 回文串长度为偶数
    }
    return res;
}

void countPalin(string &s, int i, int j, int &res) {
    while(i>=0 && j<s.size() && s[i--]==s[j++]) ++res;
}

    #DP

    636. Exclusive Time of Functions687. Longest Univalue Path