72. Edit Distance Leetcode Java

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:

Dynamic programming

If we use a 2-d array to store the information that for till i in word1 and j in word2, the minimum number of steps to convert word1(0,i) to word2(0,j)

It is not hard to see that if word1.charAt(i)==word2.charAt(j), res[i][j]=res[i-1][j-1], because no operation is needed.

But if they are not the same, we can have 3 operations to convert them.

Insert a character: res[i][j]=res[i-1][j]+1;

Delete a character: res[i][j]=res[i][j-1]+1;

Replace a character: res[i][j]=res[i-1][j-1]+1;

We need to find the minimum of them and assign to res[i][j]

A little trick here is that consider the string as empty string when i=0 or j=0, this will help process the first char of two strings more efficient.

Again a 1-d array is efficient to take care of the required information but may make code a little bit harder to understand.

Time complexity: O(m*n)

  public int minDistance(String word1, String word2) {  
     if(word1==null || word2==null) return 0;  
     int[] res= new int[word2.length()+1];  
     for(int i=-1;i<word1.length();i++){  
       int[] newRes=new int[word2.length()+1];  
       newRes[0]=i+1;  
       for(int j=0;j<word2.length();j++){  
       if(i==-1) newRes[j+1]=j+1;  
       else if(word1.charAt(i)==word2.charAt(j)) newRes[j+1]=res[j];  
       else {  
         newRes[j+1]=Math.min(Math.min(res[j],res[j+1]),newRes[j])+1;  
         }  
       }  
      res=newRes;  
      }  
     return res[word2.length()];  
   }