简介：编辑距离 hard
2 动态规划设计
2.6 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
示例 1：
1
2
3
4
5
6
|
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
|
示例 2：
1
2
3
4
5
6
7
8
|
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
|
提示：
- 0 <= word1.length, word2.length <= 500
- word1 和 word2 由小写英文字母组成
解法一
暴力递归 –> 超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public int minDistance(String word1, String word2) {
return dp(word1, word2, word1.length() - 1, word2.length() - 1);
}
public int dp(String word1, String word2, int i, int j) {
//递归出口
if(i == -1) return j + 1;
if(j == -1) return i + 1;
//递归体
if(word1.charAt(i) == word2.charAt(j)) {
return dp(word1, word2, i-1, j-1);
} else {
int a = dp(word1, word2, i, j-1);
int b = dp(word1, word2, i-1, j);
int c = dp(word1, word2, i-1, j-1);
return min(a, b, c) + 1;
}
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
|
解法二
dpTable 优化的递归 击败了6.23%的用户
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
|
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length(), n2 = word2.length();
int[][] dpTable = new int[n1 + 1][n2 + 1];
for(int[] nums : dpTable) {
Arrays.fill(nums, n1);
}
dp(word1, word2, n1, n2, dpTable);
return dpTable[n1][n2];
}
public void dp(String word1, String word2, int i, int j, int[][] dpTable) {
int n1 = word1.length(), n2 = word2.length();
//递归出口
if(i == 0){
dpTable[i][j] = j;
return;
}
if(j == 0){
dpTable[i][j] = i;
return;
}
//递归体
if(dpTable[i][j-1] >= n1) dp(word1, word2, i, j-1, dpTable);
if(dpTable[i-1][j] >= n1) dp(word1, word2, i-1, j, dpTable);
if(dpTable[i-1][j-1] >= n1) dp(word1, word2, i-1, j-1, dpTable);
int a = dpTable[i][j-1];
int b = dpTable[i-1][j];
int c = dpTable[i-1][j-1];
if(word1.charAt(i-1) == word2.charAt(j-1)) {
dpTable[i][j] = c;
} else {
dpTable[i][j] = min(a, b, c) + 1;
}
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
|
解法三
自下而上 动态规划 击败了87.28%的用户
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
|
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length(), n2 = word2.length();
//1. 定义dp数组:dp[i][j]代表word1[0~i-1]和word2[0~j-1]的最小距离
int[][] dp = new int[n1 + 1][n2 + 1];
//2. base case
for(int i = 0; i <= n1; i++) {
dp[i][0] = i;
}
for(int j = 0; j <= n2; j++) {
dp[0][j] = j;
}
//3. 状态转移方程
for(int i = 1; i <= n1; i++) {
for(int j = 1; j <= n2; j++) {
if(word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
}
}
}
//4. 返回值
return dp[n1][n2];
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
|
解法四
不难发现：dp[i][j]仅仅与dp[i-1][j-1],dp[i][j-1],dp[i-1][j]的状态有关，所以可以进行状态压缩，减小空间复杂度
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
|
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length(), n2 = word2.length();
//1. 定义dp数组:dp[j]代表word1[0~i-1]和word2[0~j-1]的最小距离
int[] dp = new int[n2 + 1];
int[] pre = new int[n2 + 1];
//2. base case
for(int j = 0; j <= n2; j++) {
dp[j] = j;
}
pre = Arrays.copyOf(dp, n2 + 1);
//3. 状态转移方程
for(int i = 1; i <= n1; i++) {
dp[0] = i; //设置每行第一个元素
for(int j = 1; j <= n2; j++) {
if(word1.charAt(i-1) == word2.charAt(j-1)) {
dp[j] = pre[j-1];
} else {
dp[j] = min(pre[j], dp[j-1], pre[j-1]) + 1;
}
}
pre = Arrays.copyOf(dp, n2 + 1);
}
//4. 返回值
return dp[n2];
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
|
