day46-dynamic programming-part13-8.17

tasks for today:

1. 647.回文子串

2. 516.最长回文子序列

--------------------------------------------------------------------

1. 647.回文子串

In this practice, it is important to figure out the essence to decide if a string a target one, the string [i,j] is based on [i+1,j-1] and if s[i] == s[j]. so dp[i][j] record if [i,j] is a target string, by juding if s[i] == s[j], result is updated (if applicable), and the dp[i][j] is decided.

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

        dp = [[False] * len(s) for _ 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]:
                    dp[i][j] = False
                else:
                    if j - i <= 1:
                        result += 1
                        dp[i][j] = True
                    elif dp[i+1][j-1]:
                        result += 1
                        dp[i][j] = True
            
        return result

2. 516.最长回文子序列

the difference of this practice from the practice 647 is that the sequence in this practice is not required as contunous.

the result should return dp[0][-1], which records the length of the logest target sequence.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s) == 1: return 1

        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][j-1], dp[i+1][j])
        
        return dp[0][-1]