来源
leetCode 647题
https://leetcode.cn/problems/palindromic-substrings/submissions/
题目描述:
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例
示例1:
输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"
示例2:
输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示:
提示:
1 <= s.length <= 1000
s 由小写英文字母组成
方案1:
双层循环,暴力解题
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let len = s.length
let res = 0
for(let i = 0;i<len;i++){
// 从左往右拼接字符串,窗口移动法
let str = ''
// 反向拼接字符串,如果正向和反向相等,表示是回文
let reverStr = ''
for(let j = i; j< len; j++){
str += s[j]
reverStr = s[j] + reverStr
if(str === reverStr){
res++
}
}
}
return res
};
方案2:
中心扩散法
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let len = s.length
let res = 0
for(let i = 0;i<len;i++){
// 中心点法
// 基数个
res += extend(i,i);
// 偶数个
res += extend(i,i+1)
}
return res
function extend(l,r){
let count = 0
while(l>=0 && r < len && s[l] === s[r]) {
//向2边扩张
l--;
r++;
count++
}
return count
}
};