72 编辑距离

一、题目

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

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

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

二、题解

思路： dp[i][j]表示：把 word1 的前 i 个字符，转换成 word2 的前 j 个字符，所需要的最少操作次数。如果当前字符相同，就继承左上角状态；如果不同，就从删除、插入、替换三种操作中选最小值再加一。

状态初始化：

  1. 如果 word2 是空字符串，那么 word1 只能一直删除：dp[i][0] = i
  2. 如果 word1 是空字符串，那么只能一直插入：dp[0][j] = j

状态转移：

  1. 情况一：两个字符相同 如果当前字符一样，不需要操作：dp[i][j] = dp[i - 1][j - 1];

  2. 情况二：两个字符不同 如果当前字符不同，有三种操作：

    1. 删除：删除 word1 当前字符：dp[i - 1][j] + 1
    2. 插入：向 word1 插入一个字符：dp[i][j - 1] + 1
    3. 替换：把 word1 当前字符替换成 word2 当前字符：dp[i - 1][j - 1] + 1 所以取三者最小值：dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j] 表示 word1 前 i 个字符转换成 word2 前 j 个字符的最少操作数
        int[][] dp = new int[m + 1][n + 1];

        // 初始化第一列：word1 前 i 个字符转换成空串，只能删除
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // 初始化第一行：空串转换成 word2 前 j 个字符，只能插入
        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++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);

                // 如果当前字符相同，不需要操作
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 当前字符不同，可以删除、插入、替换，取最小值
                    dp[i][j] = Math.min(
                            Math.min(dp[i - 1][j], dp[i][j - 1]),
                            dp[i - 1][j - 1]
                    ) + 1;
                }
            }
        }

        return dp[m][n];
    }
}

时间复杂度：O(m * n) 空间复杂度：O(m * n)

评论