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 int len1 = word1.length(); 4 int len2 = word2.length(); 5 int dp[][] = new int[len1+1][len2+1]; 6 for(int i=0;i<=len1;i++){ 7 for(int j=0;j<=len2;j++){ 8 if(i==0){ 9 dp[i][j]=j; 10 } 11 else if(j==0){ 12 dp[i][j]=i; 13 } 14 else if(word1.charAt(i-1)==word2.charAt(j-1)){ 15 dp[i][j] = dp[i-1][j-1]; 16 } 17 else{ 18 dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1; 19 } 20 } 21 } 22 return dp[len1][len2]; 23 } 24 }
原文：http://www.cnblogs.com/krunning/p/3538764.html
