[leetcode]Edit distance

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

编程之美上的原题，但是书中给出的答案是递归实现，但是不知道给出答案的原作者难道没有测试吗？

很小的case都会超时，例如："trinitrophenylmethylnitramine", "dinitrophenylhydrazine"

递归版：

 1 public class Solution {
 2     public int minDistance(String word1, String word2) {
 3         if(word1 == null || word1.length() == 0) return word2.length();
 4         if(word2 == null || word2.length() == 0) return word1.length();
 5         if(word1.length() > word2.length()) return minDistance(word2,word1);//assume word1 is shorter than 2
 6         if(word1.charAt(0) == word2.charAt(0)){
 7           return minDistance(word1.substring(1),word2.substring(1));  
 8         }else {
 9             int delete = minDistance(word1,word2.substring(1)) + 1;
10             int change = minDistance(word1.substring(1),word2.substring(1)) + 1;
11             return Math.min(delete,change);
12         }
13     }
14 }

View Code

这道题在wiki百科中有比较详细的讲解。具体实现用的DP：

DP算法：

维护一个二维矩阵来记录distance的状态：
dinstance[i][j]分别表示字符串word1[0~i]与word2[0~j]的距离
这里需要将distance开到[word1.length() +1][word2.length() + 1]

其中[0][0]表示二者都为空串时，distance显然为0.
当i = 0时，distance[0][j] = j （其中 1 <= j <= word2.length()），同理
当j = 0时，distance[i][0] = i （其中 1 <= i <= word1.length()）

而distance[i][j]有两种情况
当word1.charAt(i) == word2.charAt(j)时，
显然distance[i][j] = distance[i-1][j - 1];

当word1.charAt(i) != word2.charAt(j)时，
需要考察distance[i - 1][j - 1]、 distance[i][j - 1]、distance[i - 1][j]分别对应了三种情况：修改word1[i] 为word2[j]、删除word2[j]、删除word1[i]，找到这三者中最小的一个数，然后+ 1（表示删除操作或者修改操作）

代码如下：

 1 public class Solution {
 2     public int minDistance(String word1, String word2) {
 3         if(word1 == null || word1.length() == 0) return word2.length();
 4         if(word2 == null || word2.length() == 0) return word1.length();
 5         if(word1.length() > word2.length()) return minDistance(word2,word1);//assume word1 is shorter than 2
 6         int height = word1.length() + 1,width = word2.length() + 1;
 7         int[][] dp = new int[height][width];
 8         for(int i = 0; i < width;i++){
 9             if(i < height){
10                 dp[i][0] = i;
11             }
12             dp[0][i] = i;
13         }
14         for(int i = 1; i < height ; i++){
15             for(int j = 1; j < width ; j++){
16                 if(word1.charAt(i - 1) == word2.charAt(j - 1)){
17                     dp[i][j] = dp[i - 1][j - 1];
18                 }else{
19                     dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
20                 }
21             }
22         }
23         return dp[word1.length()][word2.length()];
24     }
25 }