编辑距离（Edit Distance）问题

题目描述

编辑距离（又称Levenshtein距离）是衡量两个字符串相似程度的经典指标。它定义为：将字符串A转换为字符串B所需的最少操作次数。允许的操作包括：

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

例如，将"horse"转换为"ros"：

• horse -> rorse（将'h'替换为'r'）
• rorse -> rose（删除第二个'r'）
• rose -> ros（删除'e'）

总操作数为3，所以编辑距离是3。

解题过程（动态规划）

1. 问题分析

• 输入：两个字符串A（长度m）和B（长度n）。
• 输出：最小编辑距离。

核心思想：比较A和B的每个字符，逐步构建最优解。

2. 定义状态

定义dp[i][j]表示子问题：将A的前i个字符转换为B的前j个字符所需的最少操作次数。

• 注意：这里i和j是指字符数，不是下标。A[0..i-1]对应前i个字符，B[0..j-1]类似。

3. 状态转移方程

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

情况分析（假设i>=1, j>=1）：

• 如果A[i-1] == B[j-1]（当前字符相等）：
  • 不需要额外操作，因此dp[i][j] = dp[i-1][j-1]。
• 如果A[i-1] != B[j-1]（当前字符不等）：
  • 从dp[i-1][j-1]转移：替换A[i-1]为B[j-1]，操作数+1。
  • 从dp[i-1][j]转移：删除A[i-1]，操作数+1。
  • 从dp[i][j-1]转移：在A的第i个位置插入B[j-1]，操作数+1。
  • 取三者最小值：dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。

4. 边界条件

• dp[0][j]：A为空字符串，转换为B的前j个字符，需要j次插入操作。所以dp[0][j] = j。
• dp[i][0]：A的前i个字符转换为空字符串，需要i次删除操作。所以dp[i][0] = i。
• dp[0][0] = 0：两个空字符串无需操作。

5. 计算顺序

从左到右、从上到下遍历i从0到m，j从0到n，填充dp表。

6. 最终结果

编辑距离 = dp[m][n]。

示例：A = "horse", B = "ros"

1. 初始化dp表（m=5, n=3）：

2. 逐行填充：

• i=1, j=1：A[0]=h, B[0]=r，不等。

  • 替换：dp[0][0]+1 = 0+1 = 1
  • 删除：dp[0][1]+1 = 1+1 = 2
  • 插入：dp[1][0]+1 = 1+1 = 2
  • 最小值1 -> dp[1][1]=1

• i=1, j=2：h vs o，不等。

  • 替换：dp[0][1]+1 = 1+1 = 2
  • 删除：dp[0][2]+1 = 2+1 = 3
  • 插入：dp[1][1]+1 = 1+1 = 2
  • 最小值2 -> dp[1][2]=2

• 同理计算i=1, j=3：h vs s -> dp[1][3]=3。

3. 继续计算：

• i=2, j=1：o vs r，不等。dp[2][1] = 1 + min(1,2,1) = 1+1=2
• i=2, j=2：o vs o，相等！dp[2][2] = dp[1][1] = 1
• 如此反复，最终得到：

最终dp[5][3]=3，与手动推算一致。

复杂度分析

• 时间复杂度：O(m×n)，需填充二维表格。
• 空间复杂度：O(m×n)。可优化到O(min(m,n))，只保留两行或一行。

代码实现（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
    
    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]

优化空间复杂度

只保留两行（或一维数组+一个变量存左上角）：

def minDistance_optimized(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    prev = [j for j in range(n + 1)]
    
    for i in range(1, m + 1):
        curr = [0] * (n + 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
    
    return prev[n]

应用场景

1. 拼写检查与自动纠正
2. DNA序列比对（生物信息学）
3. 自然语言处理（如机器翻译评估）
4. 模糊字符串匹配（搜索引擎、数据库查询）