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
Solution:
http://blog.163.com/gjx_12358@126/blog/static/895363452014232191498
可以通过画一张2维的表来进行查看。
1 public class Solution { 2 public int minDistance(String word1, String word2) { 3 int N1=word1.length(); 4 int N2=word2.length(); 5 int[][] dp=new int[N1+1][N2+1]; 6 for(int i=0;i<=N1;++i){ 7 dp[i][0]=i; 8 } 9 for(int j=0;j<=N2;++j){ 10 dp[0][j]=j; 11 } 12 for(int i=1;i<=N1;++i){ 13 for(int j=1;j<=N2;++j){ 14 if(word1.charAt(i-1)==word2.charAt(j-1)){ 15 dp[i][j]=dp[i-1][j-1]; 16 }else{ 17 dp[i][j]=Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1; 18 } 19 } 20 } 21 return dp[N1][N2]; 22 } 23 }
原文：http://www.cnblogs.com/Phoebe815/p/4039373.html