编辑距离

动态规划

说明

比较插入、删除和替换三种代价；二维 DP 时间 O(nm)。

分析

dp[i][j] 是把第一个前缀改成第二个前缀所需的最少操作数。最后字符相同时沿对角线继承，否则在插入、删除和替换三种操作中取最小代价。

图解推演

以 kitten→sitting 为例，可替换 k→s、替换 e→i，再插入 g，共 3 次。状态只比较前缀，删除对应 dp[i−1][j]+1，插入对应 dp[i][j−1]+1，替换对应 dp[i−1][j−1]+1；空前缀边界分别是 i 和 j。三条候选取最小，而不是固定先替换。

查看图表代码

适用前提与边界

示例按字节计操作；中文字符级编辑距离应把输入转成 rune。

示例输入与调用

fmt.Println(EditDistance("kitten", "sitting"))

运行输出

3

完整 Go 示例

package main

import "fmt"

func EditDistance(a, b string) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
		dp[i][0] = i
	}
	for j := range dp[0] {
		dp[0][j] = j
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			cost := 0
			if a[i-1] != b[j-1] {
				cost = 1
			}
			dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
		}
	}
	return dp[len(a)][len(b)]
}

func main() {
	fmt.Println(EditDistance("kitten", "sitting"))
}