leetcode [647] 回文子串

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

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

示例 1:

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

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

输入的字符串长度不会超过1000。

来自题解:

遍历字符串，对于每个字符，分两种情况讨论：

1. 回文串是奇数长度，即当前字符是中心字符，因此从左右两侧开始扩展检查是否是回文串
2. 回文串是偶数串，因此以当前字符和右字符为中心，往两侧扩展检查

class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        i = 0
        while i < len(s):
            count += self.countPalindrome(s, i, i)
            count += self.countPalindrome(s, i, i + 1)
            i += 1
        return count

    def countPalindrome(self, s: str, left, right) -> int:
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count