友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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"，结果即为 100101101+101 = 403 。 如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
提示:
-
0 <= s1.length, s2.length <= 1000 -
s1和s2由小写英文字母组成
思路分析
动态规划！
从后向前，如果遇到相等字符串则向前移动，否则舍弃其中一个结尾，向前探索。
-
一刷(暴力破解)
-
一刷(备忘录)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* 暴力破解 （63 / 93）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-24 22:36:43
*/
public int minimumDeleteSum(String s1, String s2) {
char[] sc1 = s1.toCharArray();
char[] sc2 = s2.toCharArray();
return dfs(sc1, sc1.length - 1, sc2, sc2.length - 1);
}
private int dfs(char[] a, int ai, char[] b, int bi) {
if (ai < 0) {
return sum(b, bi);
}
if (bi < 0) {
return sum(a, ai);
}
if (a[ai] == b[bi]) {
return dfs(a, ai - 1, b, bi - 1);
} else {
return Math.min(dfs(a, ai - 1, b, bi) + (int) a[ai],
dfs(a, ai, b, bi - 1) + (int) b[bi]);
}
}
private int sum(char[] a, int ai) {
int result = 0;
for (int i = 0; i <= ai; i++) {
result += a[i];
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* 暴力破解 （63 / 93）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-24 22:36:43
*/
public int minimumDeleteSum(String s1, String s2) {
char[] sc1 = s1.toCharArray();
char[] sc2 = s2.toCharArray();
return dfs(sc1, sc1.length - 1, sc2, sc2.length - 1);
}
private int dfs(char[] a, int ai, char[] b, int bi) {
if (ai < 0) {
return sum(b, bi);
}
if (bi < 0) {
return sum(a, ai);
}
if (a[ai] == b[bi]) {
return dfs(a, ai - 1, b, bi - 1);
} else {
return Math.min(dfs(a, ai - 1, b, bi) + (int) a[ai],
dfs(a, ai, b, bi - 1) + (int) b[bi]);
}
}
private int sum(char[] a, int ai) {
int result = 0;
for (int i = 0; i <= ai; i++) {
result += a[i];
}
return result;
}