-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEditDistance.java
More file actions
78 lines (71 loc) · 2.09 KB
/
EditDistance.java
File metadata and controls
78 lines (71 loc) · 2.09 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
//
// 你可以对一个单词进行如下三种操作：
//
//
// 插入一个字符
// 删除一个字符
// 替换一个字符
//
//
//
//
// 示例 1：
//
// 输入：word1 = "horse", word2 = "ros"
//输出：3
//解释：
//horse -> rorse (将 'h' 替换为 'r')
//rorse -> rose (删除 'r')
//rose -> ros (删除 'e')
//
//
// 示例 2：
//
// 输入：word1 = "intention", word2 = "execution"
//输出：5
//解释：
//intention -> inention (删除 't')
//inention -> enention (将 'i' 替换为 'e')
//enention -> exention (将 'n' 替换为 'x')
//exention -> exection (将 'n' 替换为 'c')
//exection -> execution (插入 'u')
//
// Related Topics 字符串 动态规划
// 👍 1147 👎 0
package leetcode.editor.cn;
/**
* [72]编辑距离
*/
public class EditDistance {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
if(n * m == 0)
return n + m;
int[][] dp = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++)
dp[i][0] = i;
for(int i = 1; i <= m; i++)
dp[0][i] = i;
for(int i = 1; i <= n; i++) {
char c1 = word1.charAt(i - 1);
for(int j = 1; j <= m; j++) {
char c2 = word2.charAt(j - 1);
if(c1 == c2) {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] - 1) + 1;
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[n][m];
}
}
//leetcode submit region end(Prohibit modification and deletion)
public static void main(String[] args) {
Solution solution = new EditDistance().new Solution();
}
}