Edit Distance

Problem:

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

Idea:

Think about the sub problems.  for any given length strings, i and j. How to get the min distance.  1) String i, to delete a character,  2) String j, to delete a character, 3) or replace a character.   

So minDistance(i ,j ) = Math.min  0f the following four sub problems

                                  minDistance(i-1,j) +1
                                 minDistance(i,j-1)+1
                                  minDistance(i-1,j-1) +1    if(stringI.charAt(i)!=stringJ.charAt(j)) ,
                                  minDistance(i-1,j-1)          if(stringI.charAt(i)==stringJ.charAt(j))

Then, we can use a two dimensional arrays to solve the problem by filling the array.

Solution:

public class Solution { 

              public int minDistance(String word1, String word2) { 

                      if(word1 == null && word2==null) return 0; if(word1==null) return word2.length();                           if(word2==null) return word1.length(); if(word1.length()==0) return word2.length();                           if(word2.length()==0) return word1.length(); int[][] result=new int[word1.length()][word2.length()]; 

                      result[0][0]=word1.charAt(0)==word2.charAt(0)?0:1; 

                      for(int i =1;i<word2.length();i++){ 

                             if(word2.charAt(i)==word1.charAt(0)){ 

                                     result[0][i]=i; 

                             }else{ result[0][i]=result[0][i-1]+1; } 

                       } 

                       for(int i =1;i<word1.length();i++){ 

                            if(word1.charAt(i)==word2.charAt(0)){ 

                                        result[i][0]=i;

                            }else{ result[i][0]=result[i-1][0]+1; } 

                       } 

                      for(int i=1;i<word1.length();i++){ 

                           for(int j=1;j<word2.length();j++){ 

                                 int localMin1 = Math.min(result[i-1][j]+1,result[i][j-1]+1); 

                                 int tmp=word1.charAt(i)==word2.charAt(j)?result[i-1][j-1]:result[i-1][j-1]+1;                                      result[i][j]=Math.min(localMin1,tmp); } } return result[word1.length()-1][word2.length()-1]; }

                     }

}