LeetCode 647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

解析：

给定一个字符串，统计其中回文子串的数量。

解法1：

考虑中心扩散法，遍历每一个位置i，然后以位置i作为中心，往两边扩散，如果两边的字符相等，则计数加1。同时要注意奇数长度和偶数长度的情况。代码如下：

class Solution {
public:
    int countSubstrings(string s) {
        int res =0;
        int len = s.size();
        for(int i = 0; i < len; i++)
        {
            count_num(s, i, i, res);//处理奇数情况
            count_num(s, i, i+1, res);//处理偶数情况
        }
        return res;
    }
    void count_num(string s, int i, int j, int& res)
    {
        while( i >=0 && j < s.size() && s[i] == s[j])
        {
            i --;
            j ++;
            res ++;
        }
    }
};

解法2：

动态规划的思路，假设dp[i][j]表示字符s从i到j是否是回文，然后i从 n-1 往0遍历，j从i往 n-1 遍历，然后看 s[i] 和 s[j] 是否相等。如果s[i]==s[j]，则若dp[i+1][j-1]是回文，则dp[i][j]为回文。另外，如果i和j挨着，或者中间间隔一个字符，此时也是回文。代码如下：

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