首页 > 代码库 > [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 }
这道题在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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。