友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco" 输出：4
提示：
-
1 <= word1.length, word2.length <= 500 -
word1和word2只包含小写英文字母
思路分析
判断最后一个字符是否相同，相同则 \(dfs(w1, i - 1, w2, j - 1)\)；否则 \(min(dfs(w1, i, w2, j - 1) + 1, dfs(w1, i - 1, w2, j) + 1)\)。注意边界条件的处理。
这道题还可以使用 1143. 最长公共子序列 和 72. 编辑距离（少了插入）的思路来求解。
-
一刷(暴力破解)
-
一刷(备忘录)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 通过 24 / 1306 个测试用例，超时
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-03-23 21:18:06
*/
public int minDistance(String word1, String word2) {
return dfs(word1, word1.length() - 1, word2, word2.length() - 1);
}
private int dfs(String word1, int i, String word2, int j) {
if (i < 0 || j < 0) {
return Math.max(i, j) + 1;
}
if (word1.charAt(i) == word2.charAt(j)) {
return dfs(word1, i - 1, word2, j - 1);
} else {
return Math.min(dfs(word1, i - 1, word2, j),
dfs(word1, i, word2, j - 1)) + 1;
}
}
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
/**
* 暴力破解（24/1306）-> 备忘录（7.12%）
*
* @author D瓜哥 · https://www.diguage.com
* @since 2026-03-23 21:18:06
*/
public int minDistance(String word1, String word2) {
Map<Integer, Integer> memo = new HashMap<>();
return dfs(word1, word1.length() - 1, word2, word2.length() - 1, memo);
}
private int dfs(String word1, int i, String word2, int j, Map<Integer, Integer> memo) {
if (i < 0 || j < 0) {
return Math.max(i, j) + 1;
}
int key = 1000 * i + j;
if (memo.containsKey(key)) {
return memo.get(key);
}
if (word1.charAt(i) == word2.charAt(j)) {
int result = dfs(word1, i - 1, word2, j - 1, memo);
memo.put(key, result);
return result;
} else {
int result = Math.min(dfs(word1, i - 1, word2, j, memo),
dfs(word1, i, word2, j - 1, memo)) + 1;
memo.put(key, result);
return result;
}
}