712. Minimum ASCII Delete Sum for Two Strings
712. Minimum ASCII Delete Sum for Two Strings
题目
Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.
Example 1:
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
Example 2:
Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
Constraints:
1 <= s1.length, s2.length <= 1000s1ands2consist of lowercase English letters.
题目大意
给定两个字符串 s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
s1 和 s2 由小写英文字母组成
示例 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 的结果，比答案更大。
解题思路
这道题和 第 1143 题 和 第 583 题 非常相似， 第 1143 题 是求最长公共子序列的长度， 第 583 题 是在求最长公共子序列长度的基础上计算删除字符的次数，本题是计算删除字符的 ASCII 值最小和。
解题思路还是一样的，只不过 base case 需要修改一下，计算最长公共子序列长度时，如果一个字符串为空，那么最长公共子序列长度必然是 0；但是这道题如果一个字符串为空，另一个字符串必然要被全部删除，所以需要计算另一个字符串所有字符的 ASCII 码之和。
关于状态转移，当 s1[i] 和 s2[j] 相同时不需要删除，不同时需要删除，所以可以利用 helper 函数计算两种情况，得出最优的结果。
其他的大同小异，就不具体展开了。
代码
/**
* @param {string} s1
* @param {string} s2
* @return {number}
*/
var minimumDeleteSum = function (s1, s2) {
const m = s1.length;
const n = s2.length;
let dp = new Array(m).fill(-1).map((i) => new Array(n).fill(-1));
// base case
const helper = (i, j) => {
let res = 0;
// 如果 s1 到头了，那么 s2 剩下的都得删除
if (i == -1) {
for (; j >= 0; j--) {
res += s2.charCodeAt(j);
}
return res;
}
// 如果 s2 到头了，那么 s1 剩下的都得删除
if (j == -1) {
for (; i >= 0; i--) {
res += s1.charCodeAt(i);
}
return res;
}
if (dp[i][j] != -1) return dp[i][j];
if (s1.charAt(i) == s2.charAt(j)) {
// s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
dp[i][j] = helper(i - 1, j - 1);
} else {
// s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
dp[i][j] = Math.min(
s1.charCodeAt(i) + helper(i - 1, j),
s2.charCodeAt(j) + helper(i, j - 1)
);
}
return dp[i][j];
};
return helper(m - 1, n - 1);
};
/**
* @param {string} s1
* @param {string} s2
* @return {number}
*/
var minimumDeleteSum = function (s1, s2) {
const m = s1.length;
const n = s2.length;
let dp = new Array(m + 1).fill(0).map((i) => new Array(n + 1).fill(0));
// base case
// 当 s2 为空串（即 j = 0）时，dp[i][0]为 s1[0..i - 1]的 ASCII 值之和
for (let i = 1; i <= m; i++) {
dp[i][0] = s1.charCodeAt(i - 1) + dp[i - 1][0];
}
// 当 s1 为空串（即 i = 0）时，dp[0][j]为 s2[0..j - 1]的 ASCII 值之和
for (let j = 1; j <= n; j++) {
dp[0][j] = s2.charCodeAt(j - 1) + dp[0][j - 1];
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
dp[i][j] = dp[i - 1][j - 1];
} else {
// s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
dp[i][j] = Math.min(
s1.charCodeAt(i - 1) + dp[i - 1][j],
s2.charCodeAt(j - 1) + dp[i][j - 1]
);
}
}
}
return dp[m][n];
};
相关题目
- [72. 编辑距离](https://leetcode.com/problems/edit-distance)
- [300. 最长递增子序列](https://leetcode.com/problems/longest-increasing-subsequence)
- [583. 两个字符串的删除操作](https://leetcode.com/problems/delete-operation-for-two-strings)