[647][中等][动态规划] 回文子串

题目描述

647. 回文子串

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

使用动态规划的思路, 参考[5][中等][动态规划] 最长回文子串中动态规划的解法.

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)

        count = 0
        cache = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i - 1, -1):
                if j - i > 1:
                    cache[i][j] = s[j] == s[i] and cache[i + 1][j - 1]
                elif j - i == 1:
                    cache[i][j] = s[j] == s[i]
                elif j == i:
                    cache[i][j] = True
                if cache[i][j]:
                    count += 1
        return count