代码随想录算法训练营第五十七天|647.回文子串、516.最长回文子序列

代码随想录算法训练营第五十七天|647.回文子串、516.最长回文子序列

题目

647.回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

class Solution:
    def countSubstrings(self, s: str) -> int:
        s_len = len(s)
        res = 0
        dp = [[0] * s_len for _ in range(s_len)]
        for i in range(s_len - 1, -1, -1):
            for j in range(i, s_len):
                if s[i] == s[j]:
                    # 相同aa or 中间只有一个数aba or 中间超过1个数abba（判读已经判断过的子序列）
                    if i == j or j - i == 1 or dp[i + 1][j - 1]:
                        res += 1
                        dp[i][j] = 1
        return res

题目

516.最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if not s:
            return res
        s_len = len(s)
        dp = [[0] * s_len for _ in range(s_len)]
        for i in range(s_len):
            dp[i][i] = 1
        for i in range(s_len - 1, -1, -1):
            for j in range(i + 1, s_len):
                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]