editDistance

计算两个字符串之间的编辑距离(Levenshtein Distance),即将一个字符串转换为另一个字符串所需的最少编辑操作次数。

输入字符串

源字符串

目标字符串

执行过程

步骤 1 / 44

初始化DP表：第0行为插入操作次数，第0列为删除操作次数

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1	0	0	0	0	0	0	0
i	2	0	0	0	0	0	0	0
t	3	0	0	0	0	0	0	0
t	4	0	0	0	0	0	0	0
e	5	0	0	0	0	0	0	0
n	6	0	0	0	0	0	0	0

速度:慢速正常快速超快

当前单元格

来源单元格

最终结果

算法说明

编辑距离（Levenshtein距离）计算将一个字符串转换为另一个字符串所需的最少编辑操作（插入、删除、替换）次数。时间复杂度O(m×n)。

函数签名

function editDistance(
  source: string,
  target: string,
  includeDpTable?: boolean
): EditDistanceResult

interface EditDistanceResult {
  distance: number
  operations: EditOperation[]
  dpTable?: number[][]
}

interface EditOperation {
  type: 'insert' | 'delete' | 'replace' | 'keep'
  sourceIndex: number
  targetIndex: number
  sourceChar?: string
  targetChar?: string
}

参数

参数名	类型	必填	说明
source	string	是	源字符串
target	string	是	目标字符串
includeDpTable	boolean	否	是否在结果中包含DP表(用于调试),默认false

返回值

类型	说明
EditDistanceResult	编辑距离结果对象

EditDistanceResult 结构:

属性	类型	说明
distance	number	最小编辑距离
operations	EditOperation[]	详细的编辑操作步骤
dpTable	number[][]	DP表(可选,仅当includeDpTable为true时)

EditOperation 结构:

属性	类型	说明
type	'insert' | 'delete' | 'replace' | 'keep'	操作类型
sourceIndex	number	源字符串位置
targetIndex	number	目标字符串位置
sourceChar	string	源字符(可选)
targetChar	string	目标字符(可选)

工作原理

1. 创建DP表: 创建一个 (m+1) × (n+1) 的二维数组,其中 m 和 n 分别是源字符串和目标字符串的长度
2. 初始化边界:
   • dp[i][0] = i (删除 i 个字符)
   • dp[0][j] = j (插入 j 个字符)
3. 填充DP表: 对每个位置,选择代价最小的操作
   • 字符相同: dp[i][j] = dp[i-1][j-1]
   • 字符不同: dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
4. 回溯构建操作序列: 从 dp[m][n] 开始回溯,记录每一步的操作
5. 返回结果: 返回最小编辑距离和操作步骤

时间复杂度: O(m×n),其中 m 和 n 是两个字符串的长度
空间复杂度: O(m×n)

应用场景: 拼写检查、DNA序列比对、文本相似度计算等