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

news/2024/9/25 15:22:33/

编辑距离

给你两个单词 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 casesString word1 = "horse";String word2 = "ros";System.out.println(solution.minDistance(word1, word2)); // Output: 3word1 = "intention";word2 = "execution";System.out.println(solution.minDistance(word1, word2)); // Output: 5}
}