题目
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：“abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：“aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
class Solution: def countSubstrings(self, s: str) -> int: num = 0 def count(start, end): while start >= 0 and end < len(s) and s[start] == s[end]: start -= 1 end += 1 nonlocal num num += 1 for i in range(len(s)): # 当字符串长度为奇数， 从最终间的数字开始 count(i, i) # 当字符串长度为偶数，从最中间左右两个数字开始 count(i, i+1) return num
时间复杂度O(n^2)
空间复杂度O(1)
