题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

解析

这道题还是用动归五部曲来分析下：
1.确定dp数组及其含义
对于大多数求子序列类的题目来说，求什么我们就定义什么，比如求回文子串的数目我们就定义成这个，但是对于这道题来说，dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系；
因此这道题，要定义dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
2.确定递推公式
还是先分为两步，如果s[i] != s[j]，那什么都不用说了，肯定是dp[i][j] = false;
如果相等，还需要再细分为以下三种情况：
一、下标 i == j，那么指向的是一个值，肯定是回文串
二、下标i - j = 1，因为此时的前提已经是s[i] == s[j]了，所以是类似与aa的，也是回文串
三、下标差大于1，那么就看dp[i+1][j-1]是不是回文串
3.初始化
初始化当然是false
4.遍历顺序，求dp[i][j]的时候，子串是dp[i+1][j-1]，相当于二维数组中的左下角位置，因此二维数组的遍历是从下到上，从左到右

func countSubstrings(s string) int {dp := make([][]bool, len(s) + 1)for i := range dp {dp[i] = make([]bool, len(s) + 1)}res := 0for i := len(s)-1; i >= 0; i-- {for j := i; j <= len(s)-1; j++ {if s[i] == s[j] {if j - i <= 1 {dp[i][j] = trueres++} else if dp[i+1][j-1] {dp[i][j] = trueres++}}} }return res
}

注意里面遍历顺序那里，为什么内层循环需要j :=i呢，因为dp数组定义的是[i,j]，所以j一定是大于i的；

---

上面的那种方法其实有点麻烦，还可以使用中心扩展法：
遍历s，以每个字母为中心扩散，判断是否为回文串
扩散时分两种情况：一个点为中心 或 两个点为中心

func countSubstrings(s string) int {n := len(s)result := 0for i := 0; i <= n-1; i++ {result += extend(s, i, i, n) // 一个点为中心result += extend(s, i, i+1, n) // 两个点为中心}return result
}
func extend(s string, i,j,n int) int{res := 0for i >= 0 && j < n && s[i] == s[j] {i-- //因为要中心扩展，所以符合条件的要在此基础上，分别向左右扩展j++res++}return res
}