Skip to content

Commit 263e769

Browse files
linwtlinwt
committed
72.编辑距离,补充注释
1 parent b75f232 commit 263e769

2 files changed

Lines changed: 20 additions & 3 deletions

File tree

‎leetcode_Java/Solution0072.java‎

Lines changed: 17 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44
/*
55
动态规划：自底向上
66
1、题目：给你两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符
7-
2、题目简化：字符串word1转换字符串word2的最少操作数
7+
2、题目简化：求字符串word1转换字符串word2的最少操作数
88
3、定义dp数组：
99
1）dp[i][j] 表示 word1 前 i 个字符转换成 word2 前 j 个字符使用的最少操作数
1010
2）扩增dp数组，int[][] dp = new int[n+1][m+1]，dp[0][0]表示两个都是空字符，首行首列表示至少其中一个字符串为空字符的情况
@@ -21,11 +21,17 @@
2121
② 删除：若此时 word1 的 0~i-1 位置与 word2 的 0~j 位置已经匹配了，此时多出了 word1 的 i 位置字符，应把它删除掉两者才变得相同，因此 dp[i][j] = dp[i - 1][j] + 1;
2222
③ 插入：若此时 word1 的 0~i 位置只是和 word2 的 0~j-1 位置匹配，此时只需要在 word1 的 i 位置后面插入一个和 word2 的 j 位置相同的字符，使得两者变得相同，因此 dp[i][j] = dp[i][j - 1] + 1;
2323
注：加1表示执行一次操作
24-
6、以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1 的前 5 个字符转换为 word2 的前 3 个字符，也就是将 horse 转换为 ros，因此有：
24+
6、举例：以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1 的前 5 个字符转换为 word2 的前 3 个字符，也就是将 horse 转换为 ros，因此有：
2525
1）dp[i-1][j-1] 表示替换操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将 word1 第五个字符替换成 word2 的第三个字符，即由 e 替换为 s
2626
2）dp[i][j-1] 表示删除操作，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾插入一个 s
2727
3）dp[i-1][j] 表示插入操作，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符
28-
7、遍历dp数组填表：两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最少操作数
28+
7、遍历dp数组填表：
29+
1）两个for循环遍历二维dp数组每个位置，根据状态转移方程计算该位置的最少操作数
30+
2）外层遍历word1，内层遍历word2。
31+
从二维数组角度看，顺序是从上到下，从左到右，所以遍历到(i,j)位置时，其左方、上方、左上方状态都已经遍历计算过了。
32+
从两个字符串角度看，两者遍历顺序都是从左到右，所以遍历到(i,j)位置时，其左边其他位置都遍历计算过了。
33+
所以求 dp[i][j] 时，dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1] 都是已知状态了
34+
3）遍历顺序决定了哪些位置是计算过的、是已知状态
2935
8、返回结果：最后一个状态就是结果
3036
3137
'' r o s
@@ -35,6 +41,14 @@
3541
r 3 2 2 2
3642
s 4 3 3 2
3743
e 5 4 4 3
44+
45+
word1[i] == word2[j] word1[i] != word2[j]
46+
word1： h r o s e h r o s e
47+
↑ ↑
48+
i i
49+
word2： r o s r o s
50+
↑ ↑
51+
j j
3852
*/
3953
class Solution {
4054
public int minDistance(String word1, String word2) {

‎leetcode_Java/Solution0115.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,9 @@
11
// 115. 不同的子序列
22

33

4+
/*
5+
6+
*/
47
class Solution {
58
public int numDistinct(String s, String t) {
69
int n = s.length(), m = t.length();

0 commit comments

Comments
 (0)