编辑距离（Edit Distance）

我将为您详细讲解编辑距离（Edit Distance）这个经典的线性动态规划问题。

问题描述

给定两个字符串 word1 和 word2，计算将 word1 转换成 word2 所需的最少操作次数。允许的操作包括：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例：

• 输入：word1 = "horse", word2 = "ros"
• 输出：3
• 解释：horse → rorse (将 'h' 替换为 'r')，rorse → rose (删除 'r')，rose → ros (删除 'e')

解题思路

第一步：定义状态

我们定义 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。

• i 的范围：0 到 len(word1)
• j 的范围：0 到 len(word2)

边界情况：

• dp[0][j] = j：将空字符串转换为 word2 的前 j 个字符，需要 j 次插入操作
• dp[i][0] = i：将 word1 的前 i 个字符转换为空字符串，需要 i 次删除操作

第二步：状态转移方程

对于每个位置 (i, j)，我们考虑三种操作：

1. 如果字符相等：word1[i-1] == word2[j-1]

   • 不需要操作，直接继承前一个状态：dp[i][j] = dp[i-1][j-1]

2. 如果字符不相等：我们有三种选择：

   • 插入：在 word1 中插入 word2[j-1]，然后匹配 word1[0:i] 和 word2[0:j-1]
     • 操作次数：dp[i][j-1] + 1
   • 删除：删除 word1[i-1]，然后匹配 word1[0:i-1] 和 word2[0:j]
     • 操作次数：dp[i-1][j] + 1
   • 替换：将 word1[i-1] 替换为 word2[j-1]，然后匹配 word1[0:i-1] 和 word2[0:j-1]
     • 操作次数：dp[i-1][j-1] + 1

因此，状态转移方程为：

如果 word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
否则:
    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

第三步：具体计算过程

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

初始化 dp 表：

    ""  "r"  "ro"  "ros"
""   0    1    2     3
"h"  1
"ho" 2
"hor"3
"hors"4
"horse"5

逐步填充表格：

1. i=1, j=1: 'h' vs 'r' → 不相等 → min(1,1,0)+1 = 1
2. i=1, j=2: 'h' vs 'ro' → 不相等 → min(2,1,1)+1 = 2
3. i=1, j=3: 'h' vs 'ros' → 不相等 → min(3,2,2)+1 = 3
4. i=2, j=1: 'ho' vs 'r' → 不相等 → min(2,1,1)+1 = 2
5. i=2, j=2: 'ho' vs 'ro' → 'o'=='o' → dp[1][1] = 1
6. i=2, j=3: 'ho' vs 'ros' → 不相等 → min(2,1,2)+1 = 2
7. 继续这个过程...

最终得到的 dp 表：

    ""  "r"  "ro"  "ros"
""   0    1    2     3
"h"  1    1    2     3
"ho" 2    2    1     2
"hor"3    2    2     2
"hors"4   3    3     3
"horse"5  4    4     3

第四步：代码实现

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

第五步：复杂度分析

• 时间复杂度：O(m × n)，其中 m 和 n 分别是两个字符串的长度
• 空间复杂度：O(m × n)，可以使用滚动数组优化到 O(min(m, n))

第六步：实际应用

编辑距离在现实生活中有广泛应用：

• 拼写检查和自动更正
• DNA序列比对
• 自然语言处理中的相似度计算
• 版本控制系统中的文件差异比较

这个算法通过动态规划优雅地解决了字符串转换的最小代价问题，是理解线性动态规划的经典范例。