【力扣-动态规划入门】【第 19 天】72. 编辑距离

标题：72. 编辑距离
难度：困难
天数：第19天,第3/3题

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = “intention”, word2 = “execution”
输出：5
解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提示：

0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成

以上来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    //动态规划  第19天  3/3   编辑距离问题
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];

        for(int i = 0 ; i <= m; i++){
            //如果word2是“”那么dp[i][0]就是对应的操作数
            dp[i][0] = i;
        }
        for(int j = 0; j <= n ; j++){
            //如果word1是“”那么dp[0][j]就是对应的操作数
            dp[0][j] = j;
        }

        for(int i = 1 ; i <= m; i++){
            for(int j = 1; j <= n ; j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    //如果相等，就不需要操作 操作数 = word1前一个字符，word2前一个字符的操作数 = dp[i-1][j-1]
                    dp[i][j] = dp[i-1][j-1];
                }else{
                 	//先把A[1...i-1] 变得跟B[1...j-1]一样，再修改A末尾的字符
                    //先把A[1...i-1] 变得跟B[1...j]  一样，再在A的末尾删除一个字符；
                    //先把A[1...i]   变得跟B[1...j-1]一样，再在A的末尾插入一个字符；
                    //三种操作中，取最小操作数的
                    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];
    }
}