题目

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

示例 1：

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

示例 2：

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

提示：

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

解答

解决回文子串问题主要的有两种方案：中心扩展和动态规划。可以针对这些方法继续做优化。

方法1：中心扩展

遍历字符串每个位置，以每个位置为中心向两边扩展，直到无法组成回文串为止，注意奇偶子串的分别考虑。

class Solution:
    def countSubstrings(self, s: str) -> int:
        if not s:
            return 0
        counter = 0

        def extent_from(left, right):
            c = 0
            while left >= 0 and right < len(s) and s[left] == s[right]:
                c += 1
                left -= 1
                right += 1
            return c

        for center in range(len(s)):
            counter += extent_from(center, center)
            counter += extent_from(center, center+1)

        return counter

方法2：动态规划

设置布尔类型的长和宽都为len(s)的dp矩阵，其中dp[i][j]表示s[i]到s[j]中间子串是否为回文子串。初始化对角线位置全部为True，其他位置为False。

注意遍历方向，为了可以在遍历过程中利用计算结果，外层循环需要从后往前，里层从前往后。递推公式为：

如果s[i]==s[j]，当ij相邻时填充dp[i][j]为True，否则为去掉两端s[i]s[j]的结果，即dp[i+1][j-1]。

否则，填充dp[i][j]为False。

最终，返回dp矩阵中所有值为True的位置的个数即可。

class Solution:
   def countSubstrings(self, s: str) -> int:
        if not s:
            return 0
        length = len(s)
        dp = [[False if i != j else True for i in range(length)] for j in range(length)]
        count = length
        for i in range(length-1, -1, -1):
            for j in range(i+1, length):
                if s[i] == s[j]:
                    dp[i][j] = True if j-i == 1 else dp[i+1][j-1]
                else:
                    dp[i][j] = False
                if dp[i][j]:
                    count += 1
        return count

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析