好的，我们这次来详细讲解 LeetCode 第 72 题「编辑距离」。

1. 题目描述

题目：
给你两个单词 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 -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

2. 问题理解与抽象

我们要计算的是两个字符串之间的“最小编辑距离”（Levenshtein distance）。
这个距离衡量的是两个字符串的相似程度，距离越小，说明两个字符串越相似。

关键点：

• 操作是对 word1 进行的，目标是变成 word2。
• 每一步只能执行插入、删除、替换中的一个操作。
• 我们要找的是最少步数。

3. 思路推导：为什么用动态规划

这个问题具有“最优子结构”特性：
假设 word1 的前 i 个字符和 word2 的前 j 个字符的编辑距离已知，那么我们可以通过这个已知结果推导出更长字符串的编辑距离。

定义状态：
设 dp[i][j] 表示将 word1 的前 i 个字符（即 word1[0..i-1]）转换成 word2 的前 j 个字符（即 word2[0..j-1]）所需的最少操作数。

4. 状态转移方程推导

我们考虑从 dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j] 到 dp[i][j] 的转移。

情况 1：word1[i-1] == word2[j-1]

• 当前两个字符相同，不需要额外操作，直接继承 dp[i-1][j-1]。
• 所以 dp[i][j] = dp[i-1][j-1]。

情况 2：word1[i-1] != word2[j-1]
此时我们需要执行一次操作，有三种可能：

1. 替换：将 word1[i-1] 替换为 word2[j-1]，这样最后一个字符就匹配了，问题转化为 dp[i-1][j-1]，然后加上替换的 1 次操作。

   • 代价：dp[i-1][j-1] + 1

2. 删除：删除 word1[i-1]，那么问题转化为 word1 的前 i-1 个字符转换成 word2 的前 j 个字符，即 dp[i-1][j]，然后加上删除的 1 次操作。

   • 代价：dp[i-1][j] + 1

3. 插入：在 word1 的第 i 个位置（即末尾）插入 word2[j-1]，这样 word2 的第 j 个字符就被匹配了，问题转化为 word1 的前 i 个字符转换成 word2 的前 j-1 个字符，即 dp[i][j-1]，然后加上插入的 1 次操作。

   • 代价：dp[i][j-1] + 1

我们要取这三种操作的最小值：
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

5. 边界条件

• 如果 word1 为空（i=0），要变成 word2 的前 j 个字符，需要 j 次插入操作。
  dp[0][j] = j

• 如果 word2 为空（j=0），word1 的前 i 个字符要变成空串，需要 i 次删除操作。
  dp[i][0] = i

• dp[0][0] = 0（两个空字符串的编辑距离为 0）

6. 动态规划表格填充示例

以 word1 = "horse", word2 = "ros" 为例：

初始化 dp 表（i 行 j 列，i 对应 word1 的前 i 个字符，j 对应 word2 的前 j 个字符）：

填充过程（只写几个关键格子）：

1. i=1, j=1：h vs r，不同
   dp[1][1] = min(dp[0][0], dp[0][1], dp[1][0]) + 1 = min(0, 1, 1) + 1 = 1（替换 h→r）

2. i=1, j=2：h vs ro，不同
   dp[1][2] = min(dp[0][1], dp[0][2], dp[1][1]) + 1 = min(1, 2, 1) + 1 = 2

3. i=2, j=1：ho vs r，不同
   dp[2][1] = min(dp[1][0], dp[1][1], dp[2][0]) + 1 = min(1, 1, 2) + 1 = 2

4. i=2, j=2：ho vs ro，最后一个字符 o 相同
   dp[2][2] = dp[1][1] = 1

5. 继续填表，最终 dp[5][3] 就是答案。

最终表（填完）：

所以答案是 dp[5][3] = 3，与示例一致。

7. 代码实现（Python）

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    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] = min(
                    dp[i - 1][j - 1],  # 替换
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j]       # 删除
                ) + 1
    return dp[m][n]

8. 复杂度分析

• 时间复杂度：O(m × n)，需要填充一个 (m+1) × (n+1) 的表格。
• 空间复杂度：O(m × n)，可以优化到 O(min(m, n))，但这里为了清晰展示保留二维 DP。

9. 总结

编辑距离是动态规划的经典问题，核心在于：

1. 定义 dp[i][j] 为子问题的最优解。
2. 通过比较末尾字符，分相等和不等两种情况讨论。
3. 不等时，考虑替换、插入、删除三种操作，取最小代价。
4. 正确处理边界条件。

这个算法不仅用于单词转换，还广泛应用于拼写检查、DNA序列比对、模糊搜索等场景。