回文子串个数

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

分析

可以按照前面做的最长回文子串的解法，在遍历中，判断子串为回文时，加上计数即可。

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    const len = s.length;
    let num = len;
    
    let DP = [];
    for(let i =0; i<len; i++) {
        DP[i] = [];
        DP[i][i] = 1;
    }
    
    for(let i = len-2; i>=0; i--) {
        for(let j=i+1; j<len; j++) {
            if(s[i] === s[j]) {
                DP[i][j] = j-i<3 ? j+1-i: DP[i+1][j-1];
            } else {
                DP[i][j] = 0;
            }
            
            if(DP[i][j]) {
                num++;
            }
        }
    }
    return num;
};

还有一种复杂度更低的方法：

• 我们只需要判断是否为回文，无需记录其长度。
• 回文特征：
  • 倘若回文长度为奇数，则从最中间字符i (j = i)出发，向两边扩散，只要s[i++] === s[j++]，则s.slice(i, j+1) 仍为回文
  • 倘若回文长度为偶数，则是从两个相邻字符i, j(j = i+1 )出发，向两边扩散，只要s[i++] === s[j++]，则s.slice(i, j+1)仍为回文

var countSubstrings = function(s) {
    const len = s.length;
    let num = 0;
    
    for(let i = 0; i< len; i++) {
        count(s, i, i);
        count(s, i, i+1);
    }
    
    function count(s, start, end) {
         while(start>=0 && end<len && s[start] === s[end]) {
             num++;
             start--;
             end++;
         }
    }
    
    return num;
};