两个字符串的最小ASCII删除和

难度: Medium

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

提示:

0 <= s1.length, s2.length <= 1000
s1 和 s2 由小写英文字母组成

Submission

运行时间: 263 ms

内存: 16.8 MB

class Solution:
    def minimumDeleteSum(self, word1: str, word2: str) -> int:
        def longestCommonSubsequence(text1, text2):
            l1 = len(text1) + 1
            l2 = len(text2) + 1
            dp = [[0] * l1 for i in range(l2)]
            text1 = list(text1)
            text2 = list(text2)
            for i in range(1, l2):
                for j in range(1, l1):
                    if text1[j - 1] == text2[i - 1]:
                        dp[i][j] = dp[i - 1][j - 1] + ord(text1[j - 1])
                    else:
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

            return dp[l2 - 1][l1 - 1]

        lcs = longestCommonSubsequence(word1, word2)
        ord1 = 0
        ord2 = 0
        for s in word1:
            ord1 += ord(s)
        for s in word2:
            ord2 += ord(s)
        return ord1 + ord2 - 2 * lcs

Explain

这个题解的思路是先求出两个字符串的最长公共子序列（Longest Common Subsequence, LCS），然后计算出两个字符串所有字符的 ASCII 码值之和，最后用两个字符串的 ASCII 码值之和减去 2 倍 LCS 的 ASCII 码值之和，得到删除的最小 ASCII 码值之和。求 LCS 的过程使用了动态规划，dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 的 ASCII 码值之和。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    def minimumDeleteSum(self, word1: str, word2: str) -> int:
        def longestCommonSubsequence(text1, text2):
            l1 = len(text1) + 1
            l2 = len(text2) + 1
            # 创建 dp 数组，dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 的 ASCII 码值之和
            dp = [[0] * l1 for i in range(l2)]
            text1 = list(text1)
            text2 = list(text2)
            for i in range(1, l2):
                for j in range(1, l1):
                    if text1[j - 1] == text2[i - 1]:
                        # 如果当前字符相等，将其 ASCII 码值加到 dp[i][j] 中
                        dp[i][j] = dp[i - 1][j - 1] + ord(text1[j - 1])
                    else:
                        # 如果当前字符不相等，取 dp[i-1][j] 和 dp[i][j-1] 的最大值
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

            # 返回 LCS 的 ASCII 码值之和
            return dp[l2 - 1][l1 - 1]

        # 计算 LCS 的 ASCII 码值之和
        lcs = longestCommonSubsequence(word1, word2)
        # 计算 word1 的 ASCII 码值之和
        ord1 = 0
        for s in word1:
            ord1 += ord(s)
        # 计算 word2 的 ASCII 码值之和
        ord2 = 0
        for s in word2:
            ord2 += ord(s)
        # 返回删除的最小 ASCII 码值之和
        return ord1 + ord2 - 2 * lcs

Explore

动态规划方法是解决最长公共子序列（LCS）问题的经典方法，因为LCS问题具有最优子结构和重叠子问题的特性。最优子结构意味着问题的最优解可以从其子问题的最优解构建。重叠子问题意味着在计算过程中，会多次解决相同的子问题。动态规划通过构建一个表格来一次性解决每个子问题，并存储其结果，避免了重复计算，从而提高了效率。

将dp[i][j]定义为text1[:i]和text2[:j]的LCS的ASCII码值之和而非仅仅是长度，提供了更多信息和灵活性。这种定义直接关联到问题的最终目标——最小化要删除的字符的ASCII值总和。通过这种方式，我们可以直接从dp数组中获得所需的LCS ASCII值之和，而无需重新遍历字符串来计算ASCII值，从而效率更高，代码更简洁。

是的，这种方法确保了最优解。在动态规划中，当字符text1[j-1]和text2[i-1]不相等时，我们需要决定是忽略text1的这个字符还是text2的这个字符，以维持最大的LCS ASCII值之和。通过比较dp[i-1][j]（忽略text2的字符）和dp[i][j-1]（忽略text1的字符）并选择两者中的最大值，我们确保了在当前字符不匹配的情况下，仍然保持最大的ASCII值之和，从而保证了结果的最优性。

dp数组的大小设置为(m+1)*(n+1)是为了方便处理边界条件，其中m和n分别是text1和text2的长度。在动态规划中，我们通常需要考虑空字符串作为一个有效的子序列。dp[i][0]和dp[0][j]分别表示text1的前i个字符和空字符串以及空字符串和text2的前j个字符的LCS的ASCII值之和。初始化这些值为0，可以使我们在填充dp表时，不需要对i=0或j=0的情况做特殊处理，从而简化代码实现。