大家好，我是吴师兄，关注我，每周更新大厂最新笔试题解析。
题目描述
给定两个字符串s1和s2，返回使两个字符用相等所需删除字符的ASCII值的最小和。
0 <= s1.length, s2.length <= 1000
s1和s2由小写英文字母组成.
输入描述
本题为LeetCode核心代码模式，传入两个参数s1和s2，为两个字符串。
输出描述
返回一个整数，为使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例一
输入
代码语言：javascript复制s1 = "sea"
s2 = "eat"
输出
代码语言：javascript复制231
说明
在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。在 "eat" 中删除 "t" 并将 116 加入总和。结束时，两个字符串相等，115 116 = 231 就是符合条件的最小和。
示例二
输入
代码语言：javascript复制s1 = "delete"
s2 = "leet"
输出
代码语言：javascript复制403
说明
在 "delete" 中删除 "dee" 字符串变成 "let"， 将 100(d) 101(e) 101(e) 加入总和。在 "leet" 中删除 "e" 将 101(e) 加入总和。结束时，两个字符串都等于 "let"，结果即为 100 101 101 101 = 403 。如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
解题思路
注意，本题为LeetCode712. 两个字符串的最小ASCII删除和原题。属于经典的LCS问题的变式。
代码
Python
代码语言：javascript复制# 题目：Bilibili2023秋招-两个字符串的最小ASCII删除和
# 作者：闭着眼睛学数理化
# 算法：DP-LCS问题变式
# 代码有看不懂的地方请直接在群上提问
class Solution:
def minimumDeleteSum(self, s1: str, s2: str) -> int:
# 分别获得s1和s2的长度
n, m = len(s1), len(s2)
# 构建大小为(n 1)*(m 1)的dp数组
# dp[i][j]表示，令
# 以s1[i-1]为结尾的字串s1[:i]
# 以s2[j-1]为结尾的字串s2[:j]
# 两者完全相同所需删除字符的ASCII值的最小和
dp = [[0] * (m 1) for _ in range(n 1)]
# 初始化dp数组中第1行、第1列的情况
for i in range(1, n 1):
dp[i][0] = dp[i-1][0] ord(s1[i-1])
for j in range(1, m 1):
dp[0][j] = dp[0][j-1] ord(s2[j-1])
for i in range(1, n 1):
for j in range(1, m 1):
ch1, ch2 = s1[i-1], s2[j-1]
# 若两个结尾字符不相等，则在以下三种情况中挑出最小值赋值给dp[i][j]
# 1. 同时删除s1[i-1]和s2[j-1]，那么从dp[i-1][j-1]转移过来，为ord(ch1) ord(ch2) dp[i-1][j-1]
# 2. 只删除s1[i-1]，保留s2[j-1]，那么从dp[i-1][j]转移过来，为ord(ch1) dp[i-1][j]
# 3. 只删除s2[j-1]，保留s1[i-1]，那么从dp[i][j-1]转移过来，为ord(ch2) dp[i][j-1]
if ch1 != ch2:
dp[i][j] = min(ord(ch1) ord(ch2) dp[i-1][j-1], ord(ch1) dp[i-1][j], ord(ch2) dp[i][j-1])
# 若两个结尾字符相等，则无需做任何删除
# 直接在dp[i-1][j-1]中延长过来即可
else:
dp[i][j] = dp[i-1][j-1]
return dp[-1][-1]
Java
代码语言：javascript复制class Solution {
public int minimumDeleteSum(String s1, String s2) {
int n = s1.length();
int m = s2.length();
int[][] dp = new int[n 1][m 1];
for (int i = 1; i <= n; i ) {
dp[i][0] = dp[i-1][0] (int)s1.charAt(i-1);
}
for (int j = 1; j <= m; j ) {
dp[0][j] = dp[0][j-1] (int)s2.charAt(j-1);
}
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j ) {
char ch1 = s1.charAt(i-1);
char ch2 = s2.charAt(j-1);
if (ch1 != ch2) {
dp[i][j] = Math.min((int)ch1 (int)ch2 dp[i-1][j-1], Math.min((int)ch1 dp[i-1][j], (int)ch2 dp[i][j-1]));
} else {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[n][m];
}
}
C
代码语言：javascript复制class Solution {
public:
int minimumDeleteSum(std::string s1, std::string s2) {
int n = s1.length();
int m = s2.length();
std::vector<std::vector<int>> dp(n 1, std::vector<int>(m 1, 0));
for (int i = 1; i <= n; i ) {
dp[i][0] = dp[i-1][0] (int)s1[i-1];
}
for (int j = 1; j <= m; j ) {
dp[0][j] = dp[0][j-1] (int)s2[j-1];
}
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j ) {
char ch1 = s1[i-1];
char ch2 = s2[j-1];
if (ch1 != ch2) {
dp[i][j] = min(ch1 ch2 dp[i-1][j-1], min(ch1 dp[i-1][j], ch2 dp[i][j-1]));
} else {
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[n][m];
}
};
时空复杂度
时间复杂度：O(NM)。双重循环所花费的时间复杂度。
空间复杂度：O(NM)。dp数组所占空间。
