Leetcode 72 - edit distance - study the code and give some code review

Leetcode72_editDistance.java

package DP;  
  
import java.util.Arrays;  
  
/** 
Dec. 30, 2017 Study the blog:
http://blog.csdn.net/fightforyourdream/article/details/13169573
 * 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 
 */  
public class EditDistance {  
  
    static int[][] dist = null;  
      
    public static void main(String[] args) {  
        String word1 = "sdfsssjdfhsb";  
        String word2 = "cvdsfadfgkdfgj";  
          
        dist = new int[word1.length()+1][word2.length()+1];  
        for(int[] row : dist){  
            Arrays.fill(row, -1);  
        }  
          
        System.out.println(minDistance(word1, word2));  
        System.out.println(minDistance2(word1, word2));  
    }  
      
    public static int min3(int a, int b, int c){  
        return Math.min(Math.min(a, b), c);  
    }  
      
    // DP bottom-up  
    public static int minDistance(String word1, String word2) {  
        int[][] distance = new int[word1.length()+1][word2.length()+1];  
          
        // 边界情况：当其中一个string为空时，只要一直添加或删除就可以  
        for(int i=0; i<=word1.length(); i++){  
            distance[i][0] = i;  
        }  
        for(int j=1; j<=word2.length(); j++){  
            distance[0][j] = j;  
        }  
          
        // 递推，[i][j]处可以由左，上，左上3种情况而来  
        for(int i=1; i<=word1.length(); i++){  
            for(int j=1; j<=word2.length(); j++){  
                distance[i][j] = min3(distance[i-1][j]+1,   // 从上演变  
                                            distance[i][j-1]+1, // 从左演变  
                                            distance[i-1][j-1]+(word1.charAt(i-1)==word2.charAt(j-1) ? 0 : 1)); 
                                            // 从左上演变，考虑是否需要替换  
            }  
        }  
        
        return distance[word1.length()][word2.length()];        // 返回右下角  
    }  
  
    // 递归，太慢  
    public static int minDistance2(String word1, String word2) {  
//      return rec(word1, word1.length(), word2, word2.length());  
        return rec2(word1, word1.length(), word2, word2.length());  
    }  
      
    public static int rec(String word1, int len1, String word2, int len2){  
        if(len1 == 0){  
            return len2;  
        }  
        if(len2 == 0){  
            return len1;  
        }  
        if(word1.charAt(len1-1) == word2.charAt(len2-1)){  
            return rec(word1, len1-1, word2, len2-1);  
        }else{  
            return min3(rec(word1, len1-1, word2, len2-1) + 1,   
                            rec(word1, len1, word2, len2-1) + 1,   
                            rec(word1, len1-1, word2, len2) + 1);  
        }  
    }  
      
    // 添加全局数组，保存状态，用空间换时间 DP top-down  
    public static int rec2(String word1, int len1, String word2, int len2){  
        if(len1 == 0){  
            return len2;  
        }  
        if(len2 == 0){  
            return len1;  
        }  
          
        if(word1.charAt(len1-1) == word2.charAt(len2-1)){  
            if(dist[len1-1][len2-1] == -1){  
                dist[len1-1][len2-1] = rec2(word1, len1-1, word2, len2-1);  
            }  
            return dist[len1-1][len2-1];  
        }else{  
            if(dist[len1-1][len2-1] == -1){  
                dist[len1-1][len2-1] = rec2(word1, len1-1, word2, len2-1);  
            }  
            if(dist[len1][len2-1] == -1){  
                dist[len1][len2-1] = rec2(word1, len1, word2, len2-1);  
            }  
            if(dist[len1-1][len2] == -1){  
                dist[len1-1][len2] = rec2(word1, len1-1, word2, len2);  
            }  
            dist[len1][len2] = min3(dist[len1-1][len2-1]+1, dist[len1][len2-1]+1, dist[len1-1][len2]+1);  
            return dist[len1][len2];  
        }  
    }  
}