Leetcode 72 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

Solution 1: DP without Space optimization, easy to understand. Time O(mn), space O(mn).

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int m=word1.length();  
     int n=word2.length();  
     int[][] dp=new int[m+1][n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) dp[i][j]=j;  
         else if (j==0) dp[i][j]=i;  
         else if (word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];  
         else dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Solution 2: Optimize Space to O(n)

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int m=word1.length();  
     int n=word2.length();  
     int[] dp=new int[n+1];  
     for (int i=0; i<=m; i++) {  
       int pre=0;  
       for (int j=0; j<=n; j++) {  
         int temp=dp[j];  
         if (i==0) dp[j]=j;  
         else if (j==0) dp[j]=i;  
         else if (word1.charAt(i-1)==word2.charAt(j-1)) dp[j]=pre;  
         else dp[j]=Math.min(pre,Math.min(dp[j],dp[j-1]))+1;  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }  
 }