【多维动态规划】Leetcode 72. 编辑距离【中等】

编辑距离

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

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

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

示例 1：

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

解题思路

这是一个经典的字符串编辑距离问题，可以使用动态规划来解决。

• 1、定义一个二维数组dp，其中dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作数。

• 2、初始化dp数组，dp[i][0]表示将word1的前i个字符转换成空字符串的最少操作数，即删除操作数为i；dp[0][j]表示将空字符串转换成word2的前j个字符的最少操作数，即插入操作数为j。

• 3、如果 word1[i - 1] 等于 word2[j - 1]，则 dp[i][j] = dp[i - 1][j - 1]，表示当前字符不需要操作。

• 4、如果 word1[i - 1] 不等于 word2[j - 1]，则
  dp[i][j]= min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1，表示当前字符需要进行插入、删除或替换操作中的一种。

  对于 dp[i][j]，有三种情况分析：

  插入操作（Insertion）： 将字符 B[j] 插入到 A 的末尾，使 A 的前 i 个字符与 B 的前 j-1 个字符相匹配，然后再插入 B[j]。因此，操作次数为 dp[i][j-1] + 1。

  删除操作（Deletion）： 将 A[i] 字符删除，使 A 的前 i-1 个字符与 B 的前 j 个字符相匹配。因此，操作次数为 dp[i-1][j] + 1。

  替换操作（Substitution）： 将 A[i] 替换为 B[j]，使 A 的前 i-1 个字符与 B 的前 j-1 个字符相匹配，然后再将 A[i] 替换为 B[j]。因此，操作次数为 dp[i-1][j-1] + (A[i] != B[j])。如果 A[i] 和 B[j] 相同，则不需要进行替换操作，操作次数为 dp[i-1][j-1]；如果不相同，则需要进行替换操作，操作次数为 dp[i-1][j-1] + 1。

Java实现

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

        int[][] dp = new int[m + 1][n + 1];
        
        //初始化dp数组第一行和第一列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        
        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    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];
    }
    
    public static void main(String[] args) {
        EditDistance solution = new EditDistance();
        
        // Test cases
        String word1 = "horse";
        String word2 = "ros";
        System.out.println(solution.minDistance(word1, word2)); // Output: 3
        
        word1 = "intention";
        word2 = "execution";
        System.out.println(solution.minDistance(word1, word2)); // Output: 5
    }
}

时间空间复杂度

• 时间复杂度：遍历了一次二维数组dp，时间复杂度为O(m * n)，其中m和n分别为word1和word2的长度。

• 空间复杂度：使用了一个二维数组dp，空间复杂度为O(m * n)。