class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
}
};
712. 两个字符串的最小ASCII删除和
给定两个字符串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 <= 1000s1 和 s2 由小写英文字母组成原站题解
javascript 解法, 执行用时: 128 ms, 内存消耗: 49.4 MB, 提交时间: 2022-11-26 17:24:32
/**
* @param {string} s1
* @param {string} s2
* @return {number}
*/
var minimumDeleteSum = function(s1, s2) {
const m = s1.length, n = s2.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] + s1[i - 1].charCodeAt();
}
for (let j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] + s2[j - 1].charCodeAt();
}
for (let i = 1; i <= m; i++) {
const code1 = s1[i - 1].charCodeAt();
for (let j = 1; j <= n; j++) {
const code2 = s2[j - 1].charCodeAt();
if (code1 === code2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j] + code1, dp[i][j - 1] + code2);
}
}
}
return dp[m][n];
};
golang 解法, 执行用时: 4 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-26 17:24:05
func minimumDeleteSum(s1 string, s2 string) int {
m, n := len(s1), len(s2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
if i > 0 {
dp[i][0] = dp[i-1][0] + int(s1[i-1])
}
}
for j := range dp[0] {
if j > 0 {
dp[0][j] = dp[0][j-1] + int(s2[j-1])
}
}
for i, c1 := range s1 {
for j, c2 := range s2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j]
} else {
dp[i+1][j+1] = min(dp[i][j+1] + int(c1), dp[i+1][j] + int(c2))
}
}
}
return dp[m][n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
python3 解法, 执行用时: 624 ms, 内存消耗: 19.6 MB, 提交时间: 2022-11-26 17:23:48
'''
假设字符串 s1 和 s2 的长度分别为 m 和 n，创建 m+1 行 n+1 列的二维数组 dp，
其中 dp[i][j] 表示使 s1[0:i] 和 s2[0:j] 相同的最小 ASCII 删除和。
上述表示中，s1[0:i] 表示 s1 的长度为 i 的前缀，s2[0:j]表示 s2 的长度为 j 的前缀。
'''
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]