代码随想训练营第五十七天（Python）｜ 647. 回文子串、516.最长回文子序列

647. 回文子串
1、中心扩散法+双指针

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            # 以 i 为中心
            res += self.countPalind(i, i, s, len(s))
            # 以 i 和 i+1 为中心
            res += self.countPalind(i, i+1, s, len(s))
        return res

    def countPalind(self, i, j, s, n):
        ret = 0
        while i >= 0 and j < n and s[i] == s[j]:
            ret += 1
            i -= 1
            j += 1
        return ret

2、动态规划

class Solution:
    def countSubstrings(self, s: str) -> int:
        # dp 数组代表 i 到 j 区间的字符串是否是回文串
        dp = [[False] * (len(s)) for _ in range(len(s))]

        res = 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
                        res += 1
                    elif dp[i+1][j-1] is True:
                        dp[i][j] = True
                        res += 1
        
        return res

516.最长回文子序列

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # dp 数组代表 s 字符串在 i 至 j 间的最大回文子序列为 dp[i][j]
        dp = [[0] * len(s) for _ in range(len(s))]
        # 初始化
        for i in range(len(s)):
            dp[i][i] = 1

        for i in range(len(s) - 1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])

        return dp[0][-1]