0712. 两个字符串的最小ASCII删除和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给定两个字符串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 由小写英文字母组成

2. 🎯 s.1 - 动态规划

c

int minimumDeleteSum(char* s1, char* s2) {
    int m = strlen(s1), n = strlen(s2);
    int** dp = (int**)malloc(sizeof(int*) * (m + 1));
    for (int i = 0; i <= m; i++) dp[i] = (int*)calloc(n + 1, sizeof(int));
    for (int i = 1; i <= m; i++) dp[i][0] = dp[i - 1][0] + s1[i - 1];
    for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] + s2[j - 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else {
                int a = dp[i - 1][j] + s1[i - 1];
                int b = dp[i][j - 1] + s2[j - 1];
                dp[i][j] = a < b ? a : b;
            }
        }
    }
    int res = dp[m][n];
    for (int i = 0; i <= m; i++) free(dp[i]);
    free(dp);
    return res;
}

js

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
  const m = s1.length,
    n = s2.length
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0))
  for (let i = 1; i <= m; i++) dp[i][0] = dp[i - 1][0] + s1.charCodeAt(i - 1)
  for (let j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] + s2.charCodeAt(j - 1)
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + s1.charCodeAt(i - 1),
          dp[i][j - 1] + s2.charCodeAt(j - 1),
        )
      }
    }
  }
  return dp[m][n]
}

py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(
                        dp[i - 1][j] + ord(s1[i - 1]),
                        dp[i][j - 1] + ord(s2[j - 1])
                    )
        return dp[m][n]

• 时间复杂度：$O(m\times n)$，其中 m 和 n 分别是两个字符串的长度
• 空间复杂度：$O(m\times n)$

算法思路：

• dp[i][j] 表示使 s1[0..i-1] 和 s2[0..j-1] 相等所需删除字符的最小 ASCII 和
• 字符相同时继承 dp[i-1][j-1]，不同时取删 s1 或删 s2 的较小值
• 初始化：dp[i][0] 为 s1 前 i 个字符的 ASCII 和，dp[0][j] 同理