來源
leetCode 647題
https://leetcode.cn/problems/palindromic-substrings/submissions/
題目描述：
給你一個字符串 s 蠢壹，請你統(tǒng)計并返回這個字符串中 回文子串 的數(shù)目牵舱。
回文字符串 是正著讀和倒過來讀一樣的字符串仰税。
子字符串 是字符串中的由連續(xù)字符組成的一個序列。
具有不同開始位置或結束位置的子串，即使是由相同的字符組成齐帚，也會被視作不同的子串元践。
示例
示例1:
輸入：s = "abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"
示例2:
輸入：s = "aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
提示：
1 <= s.length <= 1000
s 由小寫英文字母組成
方案1:
雙層循環(huán)，暴力解題
/**
* @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++){
// 中心點法
// 基數(shù)個
res += extend(i,i);
// 偶數(shù)個
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
}
};
