题目描述

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

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

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

样例

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


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

算法1

(动态规划) $O(n^2)$

先读懂题目:
要对word1 进行增，删，换字符，使得word1 == word2 的最小操作次数是多少？
增: 给word1 增加字符,从哪个位置增加都可以。
换: word1 和word2 互换字符
删: word1 自行删除字符

状态变量:
f[i][j] : 代表word1 的第i 个字符和word2 的第j 个字符相等时的最小操作次数.

状态计算:
动态规划一个很重要的思路，从后往前思考。
后：此时的word1 和word2 字符串相等，那么word1 的第i 个字符和word2 的第j 个字符必然相等(i == j)。在这里我们统一操作word1 ，word2 的最后一个字符。

前：既然第i 和第j 个字符相等,那在还没有进行操作之前的情况是怎样的？ 题目中给到的操作情况有3 种：插入，删，换。

·插入：此时只要给word2 的word2[j] 字符添加到word1 的最后一个位置，就能让word1 == word2，那么此时word2[j - 1] == word1[i] (i == j-1)，即此时word2 的倒数第二个字符和word1 的最后一个字符相等，那么执行插入操作时，word2 的最后一个字符加入到word1 的最后面时，此时word1 == word2. 即f[i][j] = f[i][j-1] + 1, 1 代表这次插入操作。

·删：执行完删操作以后,word1[i] == word2[j] (i == j),那么在执行删除操作之前(word1 进行删除最后一个字符之前),word1[i-1] == word2[j] (i-1 == j),所以当word1 删除了word[i] 字符以后，才能使得word1 == word2，即f[i][j] = f[i-1][j] + 1, 1代表这一次删除操作。

·换: 执行完交换操作以后，word1[i] == word2[j] (i == j),那么在执行交换操作之前,word1[i-1] == word2[j-1] (i - 1 == j - 1), 但是有一种特殊情况，那么就是word1[i] 本来就等于word2[j],所以此时根本不需要交换操作。所以此时f[i][j] = f[i-1][j-1] + (word1[i) == word2[j] ? 0 : 1)

而我们要做的，就是把上面3 中操作情况的最小值得到，然后继续后面的操作。
这其实有点像递归的，一个大的问题是由一个一个相同属性的小的问题的结果递推得出来的。

时间复杂度

O(n^2)

参考文献

https://www.bilibili.com/video/BV15441117yb

如果觉得上面文字太晦涩的话，可以去下面连接的题解中看看图解PPT：
https://leetcode-cn.com/problems/edit-distance/solution/edit-distance-by-ikaruga/

Java 代码

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(),m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++) dp[i][0] = i;//当word2 为空字符串时,word1 只用删除自身字符就能 == word2 时的各种删除次数。
        for(int i = 1; i <= m; i++) dp[0][i] = i;//当word1 为空字符串时,word1 只需要加入字符就能 == word2 时的各种插入次数

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                dp[i][j] = Math.min(dp[i][j-1] + 1,dp[i-1][j] + 1);
                dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1] +(word1.charAt(i-1) == word2.charAt(j-1)? 0:1));
            }
        }
        return dp[n][m];
    }
}