Edit Distance

https://leetcode.com/problems/edit-distance/
给定两个字符串word1,word2，求从word1变到word2所需要的最小步骤，没次变化只能是增删改其中一个字母
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

• 例子：
  s1="bbc" ,s2="abcd"
  ||∅|a|b|c|d|
  |---|---|---|---|---|---|
  |∅ |0|1|2|3|4|
  |b |1|1|1|2|3|
  |b |2|2|1|2|3|
  |c |3|3|2|1|2|
  状态转移方程

if(word1(i-1) == word2(j-1)){
    dp[i][j] = dp[i-1][j-1];
}else{
    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
}

• 代码

public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        //翻译翻译
        //从word1转为空的情况，只能全做删除
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        //翻译翻译
        //从空转为word2的情况，只能一个一个加
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //翻译翻译
                //如果word1的当前字符等于word2的当前字符，那他们的转换次数与上一个字符的次数相等
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //dp[i - 1][j - 1] + 1 代表修改
                    //dp[i - 1][j] + 1 代表删除
                    //dp[i][j-1] + 1 代表插入
                    //细细的品味下
                    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];
    }