编辑距离（Edit Distance）
📌 定义
编辑距离（也称Levenshtein距离）是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。允许的编辑操作包括：
- 插入一个字符
- 删除一个字符
- 替换一个字符
核心思路
使用动态规划求解，定义状态：
dp[i][j]表示将word1[0...i-1]转换为word2[0...j-1]所需的最少操作次数
word1 = "horse"
word2 = "ros"
转换过程:
horse → rorse (替换h为r)
rorse → rose (删除r)
rose → ros (删除e)
编辑距离 = 3
💡 状态转移方程
设 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作次数。
边界是空字符串：
dp[i][0] = i：只能连续删除i个字符。dp[0][j] = j：只能连续插入j个字符。
当 word1[i-1] == word2[j-1] 时，最后一个字符不需要操作：
dp[i][j] = dp[i-1][j-1]
否则最后一步只有三种选择：
| 最后一步 | 转移 | 含义 |
|---|---|---|
删除 word1[i-1] | dp[i-1][j] + 1 | word1 少看一个字符 |
插入 word2[j-1] | dp[i][j-1] + 1 | 先让 word1 多出一个目标字符 |
替换 word1[i-1] | dp[i-1][j-1] + 1 | 两边各少看一个字符 |
因此：
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
为什么这样不会漏解
任意一次最优转换的最后一步，必然属于删除、插入、替换或无需操作四种情况。枚举最后一步，再从更短的前缀转移，就把所有可能的最优方案覆盖了。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(m×n) | m和n分别是两个字符串的长度 |
| 空间复杂度 | O(m×n) | 需要二维DP数组 |
| 优化空间 | O(min(m,n)) | 滚动数组优化 |
Go 代码
Go 实现
package main
import "fmt"
func minDistance(word1, word2 string) int {
m, n := len(word1), len(word2)
if m == 0 {
return n
}
if n == 0 {
return m
}
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 初始化
for i := 0; i <= m; i++ {
dp[i][0] = i
}
for j := 0; j <= n; j++ {
dp[0][j] = j
}
// 填充DP表
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
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]+1, // 插入
dp[i-1][j-1]+1, // 替换
)
}
}
}
return dp[m][n]
}
func min(a, b, c int) int {
result := a
if b < result {
result = b
}
if c < result {
result = c
}
return result
}
func main() {
word1 := "horse"
word2 := "ros"
fmt.Printf("'%s' → '%s' 的编辑距离: %d\n",
word1, word2, minDistance(word1, word2))
}🎯 DP表格示例
word1 = "horse"
word2 = "ros"
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
dp[5][3] = 3 (答案)
经典题目
基础应用
- 编辑距离 - LeetCode 72
- 两个字符串的删除操作 - LeetCode 583
变体
⚖️ 优缺点
优点
- ✅ 经典DP问题：理解动态规划的好例子
- ✅ 应用广泛：拼写纠错、文本相似度等
- ✅ 可扩展：可以自定义操作代价
缺点
- ❌ 时间复杂度O(mn)：大字符串计算慢
- ❌ 空间复杂度高：虽然可以优化到O(n)
🎨 应用场景
- 拼写纠错：查找最相似的正确单词
- DNA序列比对：计算基因序列相似度
- 文本相似度：计算两个文档的相似程度
- diff工具：文件版本对比
- 模糊搜索：容错搜索
💡 编辑距离的变体
1. 带权编辑距离
如果插入、删除、替换的代价不同，只需要把转移中的 +1 替换成对应代价，状态定义和遍历顺序不变。
2. 最长公共子序列（LCS）
编辑距离的特殊情况（只允许插入和删除）：
如果只允许插入和删除，设两个字符串长度分别为 m、n，则：
distance = m + n - 2 × LCS(word1, word2)
3. 滚动数组优化
当前行只依赖上一行和当前行左侧的值，因此可以把二维数组压缩成一维数组，空间降为 O(min(m, n))。压缩时要额外保存左上角的旧值，避免覆盖 dp[i-1][j-1]。