给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings
参考：
python
# 0647.回文子串
class Solution:
def countSubstrings(self, s: str) -> int:
"""
动态规划，回文, 时间空间O(n^2)
1.dp及下标
- 布尔类型的dp[i][j]：表示区间范围[i,j]
（注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false
2.递推公式
- s[i] != s[j] -> dp[i][j]=false
- s[i] == s[j]
- 情况1，i j指向同个字符， 如”a“
- 情况2，i与j相差1, 如”aba“，与情况1合并
- 情况3，i与j同， 接下来看i+1与j-1是否true
3.初始化
- flase
4.遍历顺序
- 从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的
:param s:
:return:
"""
dp = [[False] * len(s) for _ in range(len(s))]
res = 0
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j]:
if j - i <= 1:
res += 1
dp[i][j] = True
elif dp[i + 1][j - 1]:
res += 1
dp[i][j] = True
return res
def countSubstrings_(self, s: str) -> int:
"""
双指针法-中心扩散， 时间O(n^2), 空间O(1)
:param s:
:return:
"""
def extend(s: str, left: int, right: int, length: int) -> int:
res = 0
while left >= 0 and right < length and s[left]==s[right]:
left -= 1
right += 1
res += 1
return res
res = 0
for i in range(len(s)):
res += extend(s, i, i, len(s))
res += extend(s, i, i+1, len(s))
return res
golang
package dynamicPrograming
// 动态规划
func countSubstrings(s string) int {
dp := make([][]bool, len(s))
for i := range dp {
dp[i] = make([]bool, len(s))
}
var res int = 0
for i:=len(s)-1;i>=0;i-- {
for j:=i;j<len(s);j++ {
if s[i] == s[j] {
if j-i <= 1 {
res++
dp[i][j] = true
} else if dp[i+1][j-1] == true {
res++
dp[i][j] = true
}
}
}
}
return res
}
// 双指针-中心扩散
func countSubstrings_(s string) int {
var res int
var extend func(s string, left, right, length int) int
extend = func(s string, left, right, length int) int {
res := 0
for left >= 0 && right < length && s[left] ==s[right] {
left--
right++
res++
}
return res
}
for i:=0;i<len(s);i++ {
res += extend(s, i, i, len(s))
res += extend(s, i, i+1, len(s))
}
return res
}