题目描述
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
方法：动态规划
判断一个字符串是不是回文字符串，既要满足两点：
- 当前字符串长度为1时，肯定是回文串；
- 确定两端的字符是否相等： s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]；
- 抛去两端字符后，内部是否是回文字符串: s [ i ? 1 ] = = s [ j + 1 ] s[i-1] == s[j+1] s[i?1]==s[j+1]；
这里在判断条件二时，
s
[
i
?
1
]
=
=
s
[
j
+
1
]
s[i-1] == s[j+1]
s[i?1]==s[j+1]的结果需要已经计算出来，因此需要确定动态规划的方向。
方向确定：从下往上（i），从左往右（j）。（这样确定一个字符串是回文串的时候，条件二就已经计算出来了）
这里需要注意的是，初始化时，对创建的n * n 的二维矩阵进行False初始化。实际上我们只计算了二维数组右上角一半的值。代码如下：
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
ans = [ [False] * n for _ in range(n)]
res = 0
for i in range(n-1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
if j - i <= 1 or ans[i+1][j-1]:
res += 1
ans[i][j] = True
return res
