一、课上练习

编程练习

1. 编辑距离问题：L3471

二、知识总结

✨ 核心思想

编辑距离（又称 Levenshtein 距离）是衡量两个字符串之间差异的一种方法。具体来说，编辑距离是将一个字符串转换成另一个字符串所需的最少编辑操作次数。

允许的编辑操作包括：

• 插入：在字符串中插入一个字符
• 删除：从字符串中删除一个字符
• 替换：将字符串中的一个字符替换为另一个字符

✨ 应用场景

编辑距离在许多领域都有广泛应用，包括自然语言处理、计算机视觉、生物信息学（如 DNA 序列分析）和其他需要文本比较或模式识别的领域。

✨ 动态规划解法

设两个字符串分别为 str1 和 str2，长度分别为 m 和 n。定义 dp[i][j] 表示 str1 的前 i 个字符转换成 str2 的前 j 个字符所需的最小编辑操作次数。

初始化

• 当 i = 0 时，dp[0][j] = j，即把空串转换为长度为 j 的字符串需要 j 次插入操作
• 当 j = 0 时，dp[i][0] = i，即把长度为 i 的字符串转换为空串需要 i 次删除操作

状态转移方程

对于 i > 0 且 j > 0：

• 如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1]（当前字符已匹配，不需要额外操作）
• 如果 str1[i-1] != str2[j-1]，则 dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1，其中：
  • dp[i-1][j-1] + 1 表示替换操作
  • dp[i][j-1] + 1 表示插入操作
  • dp[i-1][j] + 1 表示删除操作

最终结果

dp[m][n] 即为 str1 转换为 str2 的最小编辑距离。

1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm> // For std::min
5
6int editDistance(const std::string& str1, const std::string& str2) {
7    int m = str1.size();
8    int n = str2.size();
9    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
10
11    // 初始化 dp 数组
12    for (int i = 0; i <= m; ++i) {
13        dp[i][0] = i; // 第一列：逐步删除所有字符
14    }
15    for (int j = 0; j <= n; ++j) {
16        dp[0][j] = j; // 第一行：逐步插入所有字符
17    }
18
19    // 填充 dp 数组
20    for (int i = 1; i <= m; ++i) {
21        for (int j = 1; j <= n; ++j) {
22            if (str1[i - 1] == str2[j - 1]) {
23                dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需操作
24            } else {
25                dp[i][j] = std::min(dp[i - 1][j - 1], // 替换操作
26                           std::min(dp[i - 1][j],     // 删除操作
27                                    dp[i][j - 1]))   // 插入操作
28                         + 1;
29            }
30        }
31    }
32
33    return dp[m][n];
34}
35
36int main() {
37    std::string str1 = "kitten";
38    std::string str2 = "sitting";
39    std::cout << "Edit Distance between '" << str1 << "' and '" << str2 << "' is "
40              << editDistance(str1, str2) << std::endl;
41    return 0;
42}

✨ 执行示例

以 str1 = "cat"，str2 = "cut" 为例，追踪 dp 表的填充过程：

初始化：

逐步填充：

dp[1][1]：str1[0]='c' == str2[0]='c'，字符相同

• dp[1][1] = dp[0][0] = 0

dp[1][2]：str1[0]='c' != str2[1]='u'

• 替换：dp[0][1] + 1 = 2
• 删除：dp[0][2] + 1 = 3
• 插入：dp[1][1] + 1 = 1
• dp[1][2] = min(2, 3, 1) = 1

dp[1][3]：str1[0]='c' != str2[2]='t'

• dp[1][3] = min(dp[0][2]+1, dp[0][3]+1, dp[1][2]+1) = min(3, 4, 2) = 2

dp[2][1]：str1[1]='a' != str2[0]='c'

• dp[2][1] = min(dp[1][0]+1, dp[1][1]+1, dp[2][0]+1) = min(2, 1, 3) = 1

dp[2][2]：str1[1]='a' != str2[1]='u'

• dp[2][2] = min(dp[1][1]+1, dp[1][2]+1, dp[2][1]+1) = min(1, 2, 2) = 1

dp[2][3]：str1[1]='a' != str2[2]='t'

• dp[2][3] = min(dp[1][2]+1, dp[1][3]+1, dp[2][2]+1) = min(2, 3, 2) = 2

dp[3][1]：str1[2]='t' != str2[0]='c'

• dp[3][1] = min(dp[2][0]+1, dp[2][1]+1, dp[3][0]+1) = min(3, 2, 4) = 2

dp[3][2]：str1[2]='t' != str2[1]='u'

• dp[3][2] = min(dp[2][1]+1, dp[2][2]+1, dp[3][1]+1) = min(2, 2, 3) = 2

dp[3][3]：str1[2]='t' == str2[2]='t'，字符相同

• dp[3][3] = dp[2][2] = 1

最终 dp 表：

答案：dp[3][3] = 1，只需要将 'a' 替换为 'u'，即 "cat" → "cut"。

✨ 解题步骤详解

解决编辑距离问题的步骤：

1. 明确三种操作：插入、删除、替换，每次操作代价为 1
2. 建立 dp 表：行对应 str1 的字符，列对应 str2 的字符，多一行一列表示空串
3. 初始化边界：空串转换为长度 j 的串需要 j 次插入，长度 i 的串转换为空串需要 i 次删除
4. 填表：字符相同则不操作（取左上角值），字符不同则取三个方向的最小值 + 1
5. 三个方向的含义：
   • 左上角 dp[i-1][j-1] + 1 → 替换
   • 上方 dp[i-1][j] + 1 → 删除 str1 的字符
   • 左方 dp[i][j-1] + 1 → 在 str1 中插入字符

✨ 常见错误

1. 三种操作对应的方向搞混：替换对应左上角，删除对应上方，插入对应左方，记错会导致理解混乱
2. 字符相同时多加了 1：当 str1[i-1] == str2[j-1] 时，dp[i][j] = dp[i-1][j-1]，不需要 +1
3. 初始化遗漏：第一行和第一列必须初始化为 0, 1, 2, 3, ...，忘记初始化会导致全部错误
4. 字符串下标偏移：dp 表中 dp[i][j] 对应的是 str1 的前 i 个字符，但字符串下标从 0 开始，所以应该比较 str1[i-1] 和 str2[j-1]
5. min 函数只比较两个值：C++ 中 min 默认只接受两个参数，三个值需要嵌套调用 min(a, min(b, c))

✨ 算法评价

• 时间复杂度：O(m×n)，需要填充整个 dp 表
• 空间复杂度：O(m×n)，用于存储 dp 数组。可以优化为 O(min(m,n))，只保留两行数据