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


Naive Way:这道题应该是DP教学题目，还是挺难的。
基本逻辑为
opt[i][j] // minimum steps to convert word1[0...i] to word2[0...j]
// base case
opt[0][j] = j, opt[i][0] = i; for all i,j
// iteration
opt[i][i] = min(opt[i-1][j] + 1, opt[i][j-1] + 1, opt[i-1][j-1]+(word1[i]==word[j]?0:1));
这个min里对应的三种情况分别是                 insert word1     insert word2               replace a character

大概是之前做过一遍吧，这次想这个逻辑想的特别转，一次通过了。

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int opt[][] = new int[word1.length()+1][word2.length()+1];  
     // base case  
     for(int i = 0;i <= word1.length();i++) opt[i][0] = i;  
     for(int j = 0;j <= word2.length();j++) opt[0][j] = j;  
     // iteration  
     for(int i = 1;i <= word1.length();i++)  
       for(int j = 1;j <= word2.length();j++)  
         opt[i][j] = Math.min(Math.min(opt[i-1][j]+1,opt[i][j-1]+1),opt[i-1][j-1] + (word1.charAt(i-1)==word2.charAt(j-1)?0:1));  
     return opt[word1.length()][word2.length()];  
   }  
 }  

Improved Way:提高DP的方法，我觉得一是看能不能消去一层循环（时间上），而是看能不能用少一维的空间（空间上）。这道题时间上应该就是这样了，空间貌似值得推敲。

自习琢磨一番，将2D的空间变成1D的。

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int opt[] = new int[word2.length()+1];  
     // base case  
     for(int j = 0;j <= word2.length();j++) opt[j] = j;  
     // iteration  
     for(int i = 1;i <= word1.length();i++){  
       int pre = i, corner = i-1;  
       for(int j = 1;j <= word2.length();j++){  
         int temp = corner;  
         corner = opt[j];  
         temp += (word1.charAt(i-1)==word2.charAt(j-1)?0:1);   
         opt[j] = Math.min(temp,Math.min(opt[j],pre)+1);  
         pre = opt[j];  
       }  
       opt[word2.length()] = pre;  
     }  
     return opt[word2.length()];  
   }  
 }