淄博营销网站建设社区营销推广活动方案

Leetcode 72.编辑距离

题目描述

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

你可以对一个单词执行以下三种操作之一：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 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 -> exention (替换 'i' 为 'e')
exention -> exection (替换 'n' 为 'c')
exection -> execuion (替换 'e' 为 'u')
execuion -> execution (替换 'i' 为 't')

Java 实现代码

public class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// dp[i][j] 表示 word1[0..i-1] 和 word2[0..j-1] 的最小编辑距离int[][] dp = new int[m + 1][n + 1];// 初始化 DP 数组for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j;  // 如果 word1 为空，需要插入 j 个字符} else if (j == 0) {dp[i][j] = i;  // 如果 word2 为空，需要删除 i 个字符} else {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];}
}

解题思路

编辑距离问题是一个经典的动态规划问题，我们可以通过动态规划来逐步解决。

1. 状态定义：

   • 定义 dp[i][j] 为 word1[0..i-1] 和 word2[0..j-1] 之间的最小编辑距离。

2. 状态转移：

   • 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]，表示如果两个字符相等，编辑距离不变。
   • 如果 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-1][j] + 1：删除一个字符。
     • dp[i][j-1] + 1：插入一个字符。
     • dp[i-1][j-1] + 1：替换一个字符。

3. 初始状态：

   • dp[i][0] = i，表示 word1[0..i-1] 和空字符串的编辑距离是 i（即删除所有字符）。
   • dp[0][j] = j，表示 空字符串 和 word2[0..j-1] 的编辑距离是 j（即插入所有字符）。

4. 目标：

   • 最终结果为 dp[m][n]，其中 m 和 n 分别是 word1 和 word2 的长度。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别是 word1 和 word2 的长度。我们需要计算一个 m x n 的 DP 表格，每个元素的计算是常数时间。

• 空间复杂度：O(m * n)，我们需要一个 m x n 的 DP 表格来存储子问题的解。

执行过程示例

假设 word1 = "horse"，word2 = "ros"，我们通过动态规划计算编辑距离。

1. 初始化 DP 数组：

   dp = [[0, 1, 2, 3],[1, 0, 0, 0],[2, 0, 0, 0],[3, 0, 0, 0],[4, 0, 0, 0],[5, 0, 0, 0]
   ]
   

2. 填充 DP 数组：

   • i = 1, j = 1，word1[0] = 'h', word2[0] = 'r'，不相等，dp[1][1] = min(dp[0][1], dp[1][0], dp[0][0]) + 1 = 1。
   • i = 1, j = 2，word1[0] = 'h', word2[1] = 'o'，不相等，dp[1][2] = min(dp[0][2], dp[1][1], dp[0][1]) + 1 = 2。
   • i = 1, j = 3，word1[0] = 'h', word2[2] = 's'，不相等，dp[1][3] = min(dp[0][3], dp[1][2], dp[0][2]) + 1 = 3。
   • i = 2, j = 1，word1[1] = 'o', word2[0] = 'r'，不相等，dp[2][1] = min(dp[1][1], dp[2][0], dp[1][0]) + 1 = 2。
   • i = 2, j = 2，word1[1] = 'o', word2[1] = 'o'，相等，dp[2][2] = dp[1][1] = 1。
   • i = 2, j = 3，word1[1] = 'o', word2[2] = 's'，不相等，dp[2][3] = min(dp[1][3], dp[2][2], dp[1][2]) + 1 = 2。
   • i = 3, j = 1，word1[2] = 'r', word2[0] = 'r'，相等，dp[3][1] = dp[2][0] = 2。
   • i = 3, j = 2，word1[2] = 'r', word2[1] = 'o'，不相等，dp[3][2] = min(dp[2][2], dp[3][1], dp[2][1]) + 1 = 2。
   • i = 3, j = 3，word1[2] = 'r', word2[2] = 's'，不相等，dp[3][3] = min(dp[2][3], dp[3][2], dp[2][2]) + 1 = 3。
   • i = 4, j = 1，word1[3] = 's', word2[0] = 'r'，不相等，dp[4][1] = min(dp[3][1], dp[4][0], dp[3][0]) + 1 = 3。
   • i = 4, j = 2，word1[3] = 's', word2[1] = 'o'，不相等，dp[4][2] = min(dp[3][2], dp[4][1], dp[3][1]) + 1 = 3。
   • `i = 4, j = 3

，word1[3] = ‘s’, word2[2] = ‘s’，相等，dp[4][3] = dp[3][2] = 2`。

• i = 5, j = 1，word1[4] = 'e', word2[0] = 'r'，不相等，dp[5][1] = min(dp[4][1], dp[5][0], dp[4][0]) + 1 = 4。
• i = 5, j = 2，word1[4] = 'e', word2[1] = 'o'，不相等，dp[5][2] = min(dp[4][2], dp[5][1], dp[4][1]) + 1 = 4。
• i = 5, j = 3，word1[4] = 'e', word2[2] = 's'，不相等，dp[5][3] = min(dp[4][3], dp[5][2], dp[4][2]) + 1 = 3。

3. 最终 DP 数组：

   dp = [[0, 1, 2, 3],[1, 1, 2, 3],[2, 2, 1, 2],[3, 2, 2, 3],[4, 3, 3, 2],[5, 4, 4, 3]
   ]
   

4. 结果为 dp[5][3] = 3，即编辑距离为 3。