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

Hint: this is a typical dynamic programming question. At a moment, the distance between two words is calculated by adding a new value to some previous values. This can be done by inserting the last character, or deleting the last character, or by replacing the last character. If the last characters are the same, the replace cost 0. All other operations cost one. Therefore, we just choose the minimum from all three possible values.

01 public int minDistance(String word1, String word2) {
02     if(word1.length()==0)   return word2.length();
03     if(word2.length()==0)   return word1.length();
04     int m=word1.length();
05     int n=word2.length();
06   
07     //Use DP, initiate an array to store previous distance values.
08     int [][] array=new int [m+1][n+1];
09   
10     for(int i=0;i<=m;i++)
11     {
12         array[i][0]=i;
13     }
14   
15     for(int j=0;j<=n;j++)
16     {
17         array[0][j]=j;
18     }
19   
20     for(int i=1;i<=m;i++)
21     {
22         for(int j=1;j<=n;j++)
23         {
24             int value=(word1.charAt(i-1)==word2.charAt(j-1))? 0 : 1;
25             array[i][j]=findMin(array[i-1][j]+1,array[i][j-1]+1,array[i-1][j-1]+value);
26         }
27     }
28   
29     return array[m][n];
30 }
31 
32 public int findMin(int a, int b, int c)
33 {
34   
35     if(a<b)
36     {
37         if(a<c)
38         {
39            return a;
40         }
41       
42         else
43         {
44             return c;
45         }
46     }
47     else
48     {
49         if(c<b)
50             return c;
51         else
52             return b;
53     }
54 }