编辑距离

周子力大约 7 分钟教学文档动态规划-二维动态规划

题目描述

解题思路

这是经典的 编辑距离（Edit Distance）问题，也称为 Levenshtein Distance，属于二维动态规划（双序列 DP）的典型应用。

✅ 问题分析

给定两个字符串 word1 和 word2，允许三种操作：

插入一个字符
删除一个字符
替换一个字符

目标：求将 word1 转换为 word2 所需的最少操作数。

✅ 动态规划思路

状态定义：

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

状态转移：

考虑 word1[i-1] 与 word2[j-1] 是否相等：

如果相等（word1[i-1] == word2[j-1]）：
- 不需要操作，直接继承：
```
dp[i][j] = dp[i-1][j-1]
```
如果不相等：
- 有三种选择，取最小值：
  - 替换：dp[i-1][j-1] + 1（把 word1[i-1] 换成 word2[j-1]）
  - 删除：dp[i-1][j] + 1（删掉 word1[i-1]）
  - 插入：dp[i][j-1] + 1（在 word1 末尾插入 word2[j-1]）
```
dp[i][j] = 1 + min(
    dp[i-1][j-1],  # 替换
    dp[i-1][j],    # 删除
    dp[i][j-1]     # 插入
)
```

初始化：

dp[0][j] = j：空字符串 → word2[:j]，需 j 次插入。
dp[i][0] = i：word1[:i] → 空字符串，需 i 次删除。

最终答案：

dp[m][n]，其中 m = len(word1), n = len(word2)

✅ Python 代码实现

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # 创建 (m+1) x (n+1) 的 DP 表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化边界
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # 填充 DP 表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # 替换
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1]       # 插入
                )
    
    return dp[m][n]

✅ 示例验证

print(minDistance("horse", "ros"))        # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5
print(minDistance("", "abc"))             # 输出: 3
print(minDistance("abc", ""))             # 输出: 3
print(minDistance("", ""))                # 输出: 0

全部正确。

⏱️ 复杂度分析

时间复杂度：O(m × n)
空间复杂度：O(m × n)

可优化至 O(min(m, n)) 空间（滚动数组），但本题规模小，无需优化。

✅ 关键理解：三种操作的对称性

删除 word1[i] ≡ 插入 word1[i] 到 word2
插入 word2[j] 到 word1 ≡ 删除 word2[j]
因此，DP 中“删除”和“插入”是对称的，体现在 dp[i-1][j] 和 dp[i][j-1] 上。

总结

编辑距离是自然语言处理、拼写检查、DNA 序列比对等领域的基础算法。掌握其 DP 建模方法，不仅能解决本题，还能迁移至：

最短变换路径
字符串相似度计算
自动纠错系统设计

此解法清晰、高效，是双序列动态规划的典范。

一、代码实现中的注意事项（易错点 & 实践细节）

1. 边界初始化必须完整

dp[0][j] = j 和 dp[i][0] = i 缺一不可。
❌ 常见错误：只初始化 dp[0][0] = 0，其余靠循环填充 → 导致第一行/列错误。
✅ 正确做法：显式初始化第一行和第一列，体现“空串到非空串”的操作数。

2. 字符比较使用 `i-1` 和 `j-1`

dp[i][j] 对应 word1[:i] 和 word2[:j]，所以实际字符是 word1[i-1] 和 word2[j-1]。
❌ 错误：if word1[i] == word2[j] → 会越界（当 i=m 时）。
✅ 始终记住：DP 表比原字符串多一行一列（哨兵设计）。

3. 二维列表创建方式

✅ 正确：[[0] * (n+1) for _ in range(m+1)]
❌ 错误：[[0] * (n+1)] * (m+1) → 所有行共享同一列表，修改一行影响全部。

这是 Python 中经典的“浅拷贝陷阱”，在 DP 中极易引发隐蔽 bug。

4. 操作语义的正确理解

删除：dp[i-1][j] + 1 → 删掉 word1 的第 i 个字符，使其匹配 word2[:j]
插入：dp[i][j-1] + 1 → 在 word1 末尾插入 word2[j]，使其匹配 word2[:j]
替换：dp[i-1][j-1] + 1 → 将 word1[i] 改为 word2[j]

✅ 关键：不要混淆“对谁操作”。DP 的视角始终是 将 word1 转为 word2。

5. 相等时不要加 1

当 word1[i-1] == word2[j-1] 时，直接继承 dp[i-1][j-1]，不能加 1。
❌ 错误写法：dp[i][j] = dp[i-1][j-1] + 1 → 会导致结果偏大。

6. 空间优化的可能性（面试加分项）

由于 dp[i][j] 只依赖上一行和当前行左侧，可用滚动数组优化到 O(n) 空间：

prev = list(range(n + 1))
curr = [0] * (n + 1)
for i in range(1, m + 1):
    curr[0] = i
    for j in range(1, n + 1):
        if word1[i-1] == word2[j-1]:
            curr[j] = prev[j-1]
        else:
            curr[j] = 1 + min(prev[j-1], prev[j], curr[j-1])
    prev, curr = curr, prev
return prev[n]

虽然本题不需要，但能体现你对 DP 本质的理解。

二、由本题得到的算法启发

1. 双序列 DP 的通用建模范式

凡是涉及两个序列的“对齐”“转换”“匹配”问题，都可以尝试：
dp[i][j] = 将 A 的前 i 个元素转换/匹配为 B 的前 j 个元素的最优代价
典型应用：
- LCS（最长公共子序列）
- 编辑距离
- 交错字符串
- 序列比对（生物信息学）

✅ 启发：掌握这一范式，可快速建模一大类问题。

2. 操作的对称性与状态转移设计

编辑距离的三种操作看似不同，但在 DP 中被统一为三种状态转移路径。
更深层理解：
- 插入和删除是互逆操作，在“将 A 转为 B”视角下，只需考虑对 A 的操作。
- 替换是“不匹配时的最小代价修正”。

✅ 启发：复杂操作可通过状态转移“编码”进 DP，无需显式模拟过程。

3. 最优子结构的体现

全局最优解（整个字符串转换）由局部最优解（前缀转换）组合而成。
例如：若已知 horse → ro 的最小操作数，再处理 's' 和 'e' 即可扩展。

✅ 启发：DP 成立的前提是问题具有最优子结构和重叠子问题——编辑距离完美满足。

4. 与现实应用的紧密联系

拼写检查：计算用户输入与词典单词的编辑距离，推荐最接近的词。
DNA 序列比对：衡量两个基因序列的相似性（常加权不同操作代价）。
版本控制 diff：Git 的 diff 算法底层基于类似思想（如 Myers diff）。
语音识别：将识别结果与标准文本对齐。

✅ 启发：基础算法是许多强大系统的基石。

5. 扩展思考：带权重的编辑距离

实际场景中，不同操作代价可能不同（如替换比插入更“昂贵”）。

只需修改转移方程中的 +1 为对应权重即可：

replace_cost = 2 if word1[i-1] != word2[j-1] else 0
dp[i][j] = min(
    dp[i-1][j-1] + replace_cost,
    dp[i-1][j] + delete_cost,
    dp[i][j-1] + insert_cost
)

这种灵活性使编辑距离模型极具实用性。

6. 与 LCS 的对偶关系

编辑距离（仅允许插入、删除、替换）与 LCS 存在数学联系：
- 若只允许插入和删除（不允许替换），则：
```
edit_distance = len(word1) + len(word2) - 2 * LCS_length
```
这揭示了不同 DP 问题之间的内在关联。

✅ 启发：算法不是孤立的，理解联系能构建知识网络。

总结

维度	关键点
实现注意	边界初始化、索引偏移、二维列表创建、操作语义、相等时不加1
算法启发	双序列 DP 范式、操作对称性、最优子结构、现实应用、可扩展性、与 LCS 关系

掌握这些细节和思想，你不仅能正确高效地解决编辑距离问题，还能将其思想迁移到更广泛的序列处理、字符串对齐和实际工程场景中。这正是算法学习的核心价值所在。