1143. 最长公共子序列(Longest Common Subsequence)

一、1143. 最长公共子序列(LCS) 1.1、题目描述

1.2.1、动态规划

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        # dp[i][j] text1前i个字符与text2前j个字符的最长公共子序列
        dp = [[0]*(n+1) for _ in range(m+1)]    # 容量比字符长度大1
        
        # 为什么要从1开始？ 因为如果两个字符不相等，需要对比前一个字符
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:  # 末端不同， 向前比较
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return dp[-1][-1]

1.2.2、动态规划+一维数组

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        # dp[j] 每次只需要前一行的数据
        dp = [0]*(n+1)    # 容量比字符长度大1
        
        for i in range(1, m+1):
            tmp = 0
            for j in range(1, n+1):
                now = dp[j]
                if text1[i-1] == text2[j-1]:
                    dp[j] = tmp + 1
                else:  # 末端不同， 向前比较
                    dp[j] = max(dp[j-1], dp[j])
                tmp = now
        return dp[-1]

二、583. 两个字符串的删除操作 2.1、题目描述

2.2.1、动态规划， 总长度-2*最长公共子序列

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        # dp[j] 每次只需要前一行的数据
        dp = [0]*(n+1)    # 容量比字符长度大1
        
        for i in range(1, m+1):
            tmp = 0
            for j in range(1, n+1):
                now = dp[j]
                if word1[i-1] == word2[j-1]:
                    dp[j] = tmp + 1
                else:  # 末端不同， 向前比较
                    dp[j] = max(dp[j-1], dp[j])
                tmp = now
        
        # 总长度-2*最长公共子序列
        return len(word1) + len(word2) - dp[-1]*2

三、712. 两个字符串的最小ASCII删除和 3.1、题目描述

3.2.1、动态规划， 最长公共子序列的变种

class Solution:
    def minimumDeleteSum(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        # dp[j] 每次只需要前一行的数据
        dp = [0]*(n+1)    # 容量比字符长度大1
        
        for i in range(1, m+1):
            tmp = 0
            for j in range(1, n+1):
                now = dp[j]
                if text1[i-1] == text2[j-1]:
                    dp[j] = tmp + ord(text1[i-1])
                else:  # 末端不同， 向前比较
                    dp[j] = max(dp[j-1], dp[j])
                tmp = now
        return self.get_total_ascii(text1) + self.get_total_ascii(text2) - 2*dp[-1]

    def get_total_ascii(self, s: str) -> int:
        total = 0
        for c in s:
            total += ord(c)
        return total