字符串编辑距离-edit distance of two strings

问题

给2个字符串str1str2. 通过对单个字符进行插入、删除或替换的方式将str1变换为str2的最小操作次数,定义为编辑距离。

输入任意字符串str1str2,输出将str1变换为str2的编辑距离。

LeetCode:72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Jupyter notebook: edit distance of two strings


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def editDistance(str1,str2):
#异常处理
if str1 is None or str2 is None:
return -1
m,n = len(str1),len(str2)
# 定义编辑距离
d = [[0]*(n+1) for _ in range(m+1)]
# 边界条件
for i in range(1,m):
d[i][0] = i
for j in range(1,n):
d[0][j] = j
# 迭代过程
for i in range(1,m+1):
for j in range(1,n+1):
if str1[i-1]==str2[j-1]:
d[i][j] = d[i-1][j-1]
else:
d[i][j] = min(d[i][j-1]+1, # 插入
d[i-1][j]+1, # 删除
d[i-1][j-1]+1) # 替换
return d[-1][-1]

测试

1
2
3
str1 ='cat'
str2 = 'mouse'
editDistance(str1,str2)

Out: 3


分析

使用动态规划(dynamic programming,DP),一般DP有两个过程:确定迭代公式和确定边界条件

确定迭代公式

d[i][j]表示str1[0:i]str2[0:j]之间的编辑距离,

str1[0:i]不包含指标(index)为i的字符。如果str1='insert', 则str1[0:3]='ins'

假设已计算出$\{d[p][q]: 0 \le p \le (i-1),0 \le q \le (j-1) \}​$。有如下两种情况:

  1. 当前字符相等:str1[i-1]==str2[j-1]

此时,只需要将字符串str1[0:i-1]转换成str2[0:j-1], 即

d[i][j]=d[i-1][j-1]

比如 $ mouse_{i-1} t\rightarrow mouse_{j-1} \Rightarrow mous_{i-2} \rightarrow mous_{j-2} ​$

  1. 当前字符不等​:str1[i-1]!=str2[j-1]

此时,就需要使用插入、删除或替换的方式处理

比如问题是 $ mouse_{i-1} \rightarrow cat_{j-1}​$

  • 插入: 在$e_{i-1}$后插入一个$t$, 问题转化为 $ mouse_{i-1} t\rightarrow cat_{j-1} \Rightarrow mouse_{i-1} \rightarrow ca_{j-2} $

从而:d[i][j]=d[i][j-1]+1

插入1次,$ mouse_{i-1} ​$修改为$ca_{j-2}​$修改d[i][j-1]

  • 删除:删除$e_{i-1}$,问题转化为$ mous_{i-2} \rightarrow cat_{j-1}$

从而:d[i][j]=d[i-1][j]+1

删除1次,$ mous_{i-2} $修改为$cat_{j-1}$修改d[i-1][j]

  • 替换:把 $e_{i-1}$替换为$t$, 问题转化为 $ moust_{i-1} \rightarrow cat_{j-1} \Rightarrow mous_{i-2} \rightarrow ca_{j-2} $

从而: d[i][j]=d[i-1][j-1]+1

替换1次,$ mous_{i-2} $修改为$ca_{j-2}$修改d[i-1][j-1]

第2种情况下,d[i][j]d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+1中最小值。

d[i][j] = min(d[i-1][j]+1,d[i-1][j-1]+1,d[i][j-1]+1)


边界条件

str1=' '时,使用插入将str1变换为str2, d[0][j]=j

' '变为 cat, 编辑次数为3次

str2=' '时,使用删除将str1变换为str2, d[i][0]=i

mouse变为' ',编辑次数5次