给定两个单词 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')
|
思路：
背包问题，动态规划
设dp(i , j) 表示word1的前i个字符组成word2的前j个字符需要的最小步数。
那么结论如下：
if( word1[i] ==word2[j] ){
那么dp(i,j)=dp(i-1,j-1);
}else{
dp(i,j) = min{ dp(i-1,j-1) dp(i-1,j) dp(i,j-1) } + 1;
}
我们分析horse转ros
|
“” |
h |
ho |
hor |
hors |
horse |
| “” |
0 |
1 |
2 |
3 |
4 |
5 |
| r |
1 |
1 |
2 |
2 |
3 |
4 |
| ro |
2 |
2 |
1 |
2 |
3 |
4 |
| ros |
3 |
3 |
2 |
2 |
2 |
3 |
我们很容易可以写出第一行跟第一列，之后一行一行的填充
word1[i] ==word2[j] 这种 case 很容易理解，
我们分析不等的case，比如 hor——》ros，
我们可以知道
- ho -> ro 最少需要1步就可以，那么hor->ros 我们只需要替换最后一位即可，
- hor -> ro最少需要2步，那么hor->ros，我们需要再插入最后一位
- ho -> ros最少需要2步，那么hor->ros,我们需要删除最后一位
我们选择其中最小的步数+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
32
| class Solution {
public int minDistance(String word1, String word2) {
if(word1==null||word2==null){
return -1;
}
int len1 = word1.length();
int len2 = word2.length();
int [][] re = new int[len1+1][len2+1];
for(int i=0;i<=len1;i++){
re[i][0]=i;
}
for(int i=0;i<=len2;i++){
re[0][i]=i;
}
for(int i=1;i<=len1;i++){
char temp1=word1.charAt(i-1);
for(int j =1 ;j <=len2;j++){
char temp2=word2.charAt(j-1);
if(temp1==temp2){
re[i][j]=re[i-1][j-1];
}else{
int s1=re[i-1][j-1]>re[i-1][j]?re[i-1][j]:re[i-1][j-1];
re[i][j]=(s1>re[i][j-1]?re[i][j-1]:s1)+1;
}
}
}
return re[len1][len2];
}
}
|