72. 编辑距离

题目链接

给你两个单词 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 <= 500
• word1 和 word2 由小写英文字母组成

解法

与 583. 两个字符串的删除操作 类似。

1. DP数组定义

对于字符串 A、B，设 dp[i][j] 表示当A 以 A[i - 1]结尾、B 以 B[j - 1] 结尾时的操作次数。

2. 状态转移方程

如果 A[i] == B[j] 那么 dp[i][j] = dp[i - 1][j - 1]，不用编辑。

如果 A[i] != B[j] 那么 dp[i][j] 可以由 dp[i - 1][j]、dp[i][j - 1] 和 dp[i - 1][j - 1]三个推导而来。

\[dp[i][j] = \left\{ \begin{aligned} & A[i-1] = B[j-1] \rightarrow dp[i-1][j-1], \quad 不用编辑 \\ & A[i-1] \neq B[j-1] \rightarrow min \left\{ \begin{aligned} &dp[i-1][j] + 1, \quad 表示A删除字符A[i-1] \\ &dp[i][j-1] + 1, \quad 表示B删除字符B[j-1]，相当于A插入字符B[j-1] \\ &dp[i-1][j-1] + 1, \quad 表示A替换字符A[i-1]为B[j-1] \end{aligned} \right. \end{aligned} \right.\]

3. 数组初始化

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j] 是一定要初始化的。

dp[i][0]：B 为空字符串，以 A[i-1] 为结尾的字符串 A 要删除多少个元素，才能和 B 相同呢，很明显 dp[i][0] = i。

dp[0][j] 的话同理，所以代码如下：

4. 最终代码

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 初始化
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
}