首页 > 代码库 > LeetCode Edit Distance
LeetCode 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
1 public class Solution { 2 public int minDistance(String word1, String word2) { 3 if (word1.equals(word2)) { 4 return 0; 5 } 6 if (word1.length()==0) { 7 return word2.length(); 8 } 9 if (word2.length()==0) {10 return word1.length();11 }12 13 int[][] distance=new int[word1.length()+1][word2.length()+1];14 for (int i = 0; i <= word1.length(); i++) {15 distance[i][0]=i;16 }17 for (int i = 0; i <= word2.length(); i++) {18 distance[0][i]=i;19 }20 21 for (int i = 1; i <= word1.length(); i++) {22 for (int j = 1; j <= word2.length(); j++) {23 if (word1.charAt(i-1)==word2.charAt(j-1)) {24 distance[i][j]=distance[i-1][j-1];25 }else {26 distance[i][j]=Math.min(Math.min(distance[i-1][j], distance[i][j-1]), distance[i-1][j-1])+1;27 }28 }29 30 }31 return distance[word1.length()][word2.length()];32 }33 }
LeetCode Edit Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。