给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
输入: "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;
};
