首页 > 代码库 > [leetcode]Edit distance

[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 }