LeetCode 647. 回文子串

题目

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

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

方法：动态规划

• dp[i][j] 表示下标为 [i, j] 组成的字符串是否为回文串，True 表示为回文串，False 表示不为回文串
• result 表示回文子串的数量
• 外部循环为从下到上的循环，内部循环为从左到右的循环
  • 若首尾字符不同，那么一定不为回文串
  • 若首尾字符相同，那么需要继续判断：若 i=j，即此时只有一个字符（e.g. a），那么一定为回文串；若 j-i=1，即只有两个字符且相等（e.g. aa），那么一定为回文串；若 j-i>1，即首尾字符间存在其他字符，那么此时应判断下标为 [i+1, j-1] 组成的字符串是否为回文串，即 dp[i+1][j-1]

class Solution(object):
    def countSubstrings(self, s):
        dp = [[False] * len(s) for row in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j - i <= 1:
                        dp[i][j] = True
                        result += 1
                    elif dp[i+1][j-1]:
                        dp[i][j] = True
                        result += 1
        return result

参考

代码相关：https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html