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

[leetcode]Edit distance

2024-07-15 09:23:40   226人阅读

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 }

 


联系
我们