当前位置：首页 > article >正文

LeetCode 72.编辑距离

article 2025/2/7 13:12:32

要解决LeetCode 72题“编辑距离”问题，我们可以使用动态规划的方法。以下是详细的C++解题思路和实现过程：

解题思路

问题分析
编辑距离问题要求将字符串 word1 转换为 word2 所需的最少操作次数，允许的操作包括插入、删除和替换字符。动态规划适用于这类具有重叠子问题和最优子结构的问题。
状态定义
定义二维数组 dp[i][j]，表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作次数。
状态转移方程
- 字符匹配：若 word1[i-1] == word2[j-1]，则无需操作，直接继承前一步的结果：
  dp[i][j] = dp[i-1][j-1]
- 字符不匹配：需从插入、删除、替换中选择操作次数最少的一种：
  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
初始化
- dp[i][0] = i：删除 i 个字符使 word1 变空。
- dp[0][j] = j：插入 j 个字符使空字符串变为 word2 的前 j 个字符。
填充顺序
按顺序遍历 i 从 1 到 m，j 从 1 到 n，确保子问题已解决。

三种操作的具体解释

你提到的三种操作对应的状态转移方程理解是正确的，但可能还不够直观。让我们通过具体场景和表格推导来彻底理解这些操作的数学含义，以及为什么最终要取这三个值的最小值。

1、操作的本质与状态转移关系

假设我们有两个字符串：

word1 = "abc"（长度 m=3）
word2 = "abd"（长度 n=3）

建立二维DP表 dp[4][4]（索引从0到3）：

i\j	0 (空)	1 (a)	2 (b)	3 (d)
0	0	1	2	3
1 (a)	1	?	?	?
2 (b)	2	?	?	?
3 ©	3	?	?	?

现在我们要计算 dp[3][3]（即 word1[0..2]转成word2[0..2]）。

场景1：插入操作（对应 `dp[i][j-1] + 1`）

当前字符：word1[2] = 'c' vs word2[2] = 'd'
插入操作：在word1末尾插入d，此时word1变为"abcd"
- 此时word1[3]的d已经匹配word2[2]的d
- 剩下的问题转化为将word1[0..2]（即"abc"）转为word2[0..1]（即"ab"）
- 这个子问题的解是 dp[3][2]
- 总操作次数 = dp[3][2] + 1

场景2：删除操作（对应 `dp[i-1][j] + 1`）

删除操作：删除word1[2]的c，此时word1变为"ab"
- 剩下的问题是将"ab"转为"abd"
- 这个子问题的解是 dp[2][3]
- 总操作次数 = dp[2][3] + 1

场景3：替换操作（对应 `dp[i-1][j-1] + 1`）

替换操作：将word1[2]的c替换为d
- 此时word1变为"abd"
- 剩下的问题是将"ab"转为"ab"
- 这个子问题的解是 dp[2][2]
- 总操作次数 = dp[2][2] + 1

2、具体数值推导

假设我们已经计算出前面的值：

i\j	0	1	2	3
0	0	1	2	3
1	1	0	1	2
2	2	1	0	1
3	3	2	1	?

现在计算 dp[3][3]：

插入：dp[3][2] + 1 = 1 + 1 = 2
删除：dp[2][3] + 1 = 1 + 1 = 2
替换：dp[2][2] + 1 = 0 + 1 = 1

最终取最小值 1，即通过替换操作只需1步。

3、为什么取三种操作的最小值？

这三种操作涵盖了所有可能的编辑方式：

插入：适用于word1比word2短的情况（需要补字符）
删除：适用于word1比word2长的情况（需要删冗余字符）
替换：适用于字符不匹配但长度相同的情况

通过动态规划，我们始终选择历史最优解（已计算的子问题最优解）加上当前操作的最小代价。

4、边界条件的深层理解

dp[i][0] = i：将长度为i的字符串变为空串，只能删除i次
dp[0][j] = j：将空串变为长度为j的字符串，只能插入j次

例如：

word1 = "abc", word2 = "" → 需要删除3次
word1 = "", word2 = "abc" → 需要插入3次

C++代码实现

#include <vector>
#include <algorithm> // 用于min函数

using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化边界条件
    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[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }) + 1;
            }
        }
    }
    return dp[m][n];
}