version at: 2020-04-06

/**
1. 状态定义: f[i][j] 是将word[1~i] 转换为 word2 [1~j]的最小操作数
2. 状态计算: 相等: w1[i] == w2[j] : f[i][j] = f[i-1][j-1]
            不等:
                替换: w1[i-1] == w2[j-1]: f[i][j] = f[i-1][j-1] + 1
                删除: w1[i] == w2[j-1]:  f[i][j] = f[i][j-1] + 1
                增加: w1[i-1] == w2[j]: f[i][j] = f[i-1][j] + 1
                以上取最小值
3. 初始状态为f[i][0]=i(全部删除) f[0][j]=j(全部添加) , 结果为f[w1.length][w2.length]            
*/

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] f = new int[word1.length()+1][word2.length()+1];

        for (int i = 0 ; i <= word1.length(); i++) f[i][0] = i;
        for (int j = 0 ; j <= word2.length(); j++) f[0][j] = j;

        for (int i = 1 ; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    f[i][j] = f[i-1][j-1];
                } else {
                    f[i][j] = 1 + Math.min(f[i-1][j-1], Math.min(f[i-1][j], f[i][j-1]));
                }
            }
        }

        return f[word1.length()][word2.length()];
    }
}

// 1. 状态定义：将 word1前 i 个字符转化为 word2 前 j 个字符的方案数最小值
// 2. 状态计算：以最后操作的 i 为分隔点划分
// 2.1 插入一个字符：word1[1...i] == word2[1...j-1] -> f[i][j-1] + 1
// 2.2 删除一个字符：word1[1...i-1] == word2[1...j] -> f[i-1][j] + 1
// 2.3 需要替换一个字符：word1[1...i-1] == word2[1...j-1] -> f[i-1][j-1] + 1
// 2.4 已经相等：f[i-1][j-1]
// 3. 边界：f[i][0] = i (删除)  f[0][j] = j(添加)


class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null && word2 == null) return 0;
        if (word1 == null ) return  word2.length();
        if (word2 == null) return word1.length();

        int n = word1.length();
        int m = word2.length();

        if (n == 0) return m;
        if (m == 0) return n;
        int len = Math.max(n,m) + 2;
        int[][] f = new int[len][len];

        // for (int i = 0 ; i < len ; i ++){
        //     for (int j = 0 ; j < len; j ++){
        //         f[i][j] = Integer.MAX_VALUE >> 1;
        //     }
        // }


        for (int i = 0 ; i <= n ; i++) f[i][0] = i;
        for (int j = 0 ; j <= m ; j++) f[0][j] = j;
        // f[0][0] = 0;  其实用不到两个空串之间不需要转移
        for (int i = 1 ; i <= n ; i++){
            for (int j = 1; j <= m; j++){
// 增加和删除不需要判断，任何情况都可进行 j>=2 和 i >=2 特判掉了从0转移的情况
//                 if (j >= 2 && word1.charAt(i-1) == word2.charAt(j-2)){
//                     f[i][j] = Math.min(f[i][j], f[i][j-1] + 1);   
//                 }

//                 if (i >= 2 && word1.charAt(i-2) == word2.charAt(j-1)){
//                     f[i][j] = Math.min(f[i][j], f[i-1][j] + 1);
//                 }

//可以简写
//                 if (word1.charAt(i-1) != word2.charAt(j-1)){
//                     f[i][j] = Math.min(f[i][j], f[i-1][j-1] + 1);
//                 }

//                 if (word1.charAt(i-1) == word2.charAt(j-1)){
//                     f[i][j] = Math.min(f[i][j], f[i-1][j-1]);
//                 }

                f[i][j] = Math.min(f[i][j-1], f[i-1][j]) + 1;
                f[i][j] = Math.min(f[i][j], f[i-1][j-1] +( word1.charAt(i-1) != word2.charAt(j-1) ? 1 : 0));
            }
        }

        return f[n][m];

    }
}