时间轴

2025-12-16

init

题目：

P72 编辑距离

https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150

这题和最长公共子序列类似：

设 $dp[i][j]$ 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数。

  • 初始化：
    • word1[0..=i]变为空字符需要 i 次操作，因此 $dp[i][0] = i$
    • 空字符串变为 word2[0..=j]需要 j 次操作，因此$dp[0][j] = j$
  • 对于dp[i][j], $i,j \ge 1$，有：
    • 如果word[i-1]==word[j-1]，那么不需要操作，$dp[i][j]=dp[i-1]dp[j-1]$
    • 否则 $dp[i][j] = min( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] ) + 1$
      • $dp[i-1][j]+1$ , 表示删除 word1[i-1]
      • $dp[i][j-1]+1$ , 表示插入 word2[j-1]
      • $dp[i-1][j-1]+1$ , 表示替换word1[i-1] 为 word2[j-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::vector;

class Solution {
    public:
        int minDistance(string word1, string word2)
        {
                // 设 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数。
                int i, j;
                int m = word1.length(), n = word2.length();
                vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
                for (i = 0; i <= m; i++) {
                        // word1[0..=i]变为空字符需要i次操作
                        dp[i][0] = i;
                }

                for (j = 0; j <= n; j++) {
                        // 空字符串变为word2[0..=j]需要j次操作
                        dp[0][j] = j;
                }

                for (i = 1; i <= m; i++) {
                        for (j = 1; j <= n; j++) {
                                if (word1[i - 1] == word2[j - 1]) {
                                        // 不需要额外操作
                                        dp[i][j] = dp[i - 1][j - 1];
                                } else {

                                        // dp[i-1][j]（删除 word1[i-1]）
                                        // dp[i][j-1]（插入 word2[j-1]）
                                        // dp[i-1][j-1]（替换 word1[i-1] 为 word2[j-1]）

                                        dp[i][j] = std::min({ dp[i][j - 1], dp[i - 1][j],
                                                              dp[i - 1][j - 1] }) +
                                                   1;
                                }
                        }
                }
                return dp[m][n];
        }
};