mock72. Edit Distance

哇，Mock的时候只在无数hints下写出来暴力解。

暴力解：time O(3^n)

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.equals(word2)){
            return 0;
        }
        if (word2 == null || word2.length() == 0){
            return word1.length();
        }
        if (word1 == null || word1.length() == 0){
            return word2.length();
        }
        int i = 0;
        while (i < word1.length() && i < word2.length() && word1.charAt(i) == word2.charAt(i)){
            i++;
        }
        int min = Integer.MAX_VALUE;
        if (i != 0){
            return minDistance(word1.substring(i), word2.substring(i));
        } else {
            //insertion
            min = Math.min(min, 1 + minDistance(word1, word2.substring(0,i) + word1.charAt(i) + word2.substring(i)));
            //deletion
            min = Math.min(min, 1 + minDistance(word1, word2.substring(0,i) + word2.substring(i+1)));
            //replacement
            min = Math.min(min, 1 + minDistance(word1, word2.substring(0,i) + word1.charAt(i) + word2.substring(i+1)));
        }
        return min;
    }
}

dp解：o（m*n)

具体的讲解可以参考一刷帖子里的视频https://www.jianshu.com/p/a29ee7ce5794
这里我简单介绍一下：

image.png

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        //convert word1 to word2
        //           word1 :  a p p l e
        //word2 
        //      a
        //      b
        //      p
        //      e
        int[][] matrix = new int[n + 1][m + 1];
        for (int i = 0; i < m + 1; i++){
            matrix[0][i] = i;
        }
        for (int i = 0; i < n + 1; i++){
            matrix[i][0] = i;
        }
        for (int i = 1; i < n + 1; i++){
            for (int j = 1; j < m + 1; j++){
                if (word1.charAt(j - 1) == word2.charAt(i - 1)){
                    matrix[i][j] = matrix[i - 1][j - 1];
                } else {
                    matrix[i][j] = 1 + Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1]));
                }
            }
        }    
        return matrix[n][m];
    }
}