给你一个字符串 s
,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"
示例 2:
输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示:
1 <= s.length <= 1000
s
由小写英文字母组成https://leetcode.cn/problems/palindromic-substrings/description/
/**
* @param {string} s
* @return {number}
*/
// 中心扩展法
var countSubstrings = function(s) {
let ans = 0;
let length = s.length;
// 总的中心点=length*2-1 (即单个字符各一种+两两字符为一种)
for(let center=0;center<length*2-1;center++){
let left = center/2;
// 右侧指针可能跟左侧是同一个,也可能是左右各一个
let right = left+center%2;
while(left>=0 && right <s.length && s.charAt(left)===s.charAt(right)){
ans++;
left--;
right++;
}
}
return ans;
};
// 动态规划
var countSubstrings = function(s) {
let ans = 0;
let length = s.length;
let dp = new Array(length).fill(0).map((item)=>new Array(length));
// 外层循环相当于右侧指针,i
// 内层循环相当于左侧指针,j
// j<=i
for(let i=0;i<length;i++){
for(let j=0;j<=i;j++){
if(s.charAt(i)===s.charAt(j)&&(i-j<2||dp[j+1][i-1])){
dp[j][i]=true;
ans++;
}
}
}
return ans;
};