647. 回文子串

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

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

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

示例 1：

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

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

学习中心扩散法的 dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func countSubstrings(s string) int {
	n := len(s)
	if n<2 {
		return n
	}
	ans := 0
	  
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
		dp[i][i] = true
		ans += 1
	}
	  
	for L:=2; L<=n; L++ {
		for i:=0; i<n-L+1; i++ {
			j := i+L-1
			if s[i] != s[j] {
				dp[i][j] = false
			} else if j-i<3 {
				dp[i][j] = true
			} else {
				dp[i][j] = dp[i+1][j-1]
			}
			  
			if dp[i][j] {
				ans += 1
			}
		}
	}
	return ans
}