问题
给2个字符串str1
和str2
. 通过对单个字符进行插入、删除或替换的方式将str1
变换为str2
的最小操作次数,定义为编辑距离。
输入任意字符串str1
和str2
,输出将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:
- Insert a character
- Delete a character
- Replace a character
Jupyter notebook: edit distance of two strings
代码
1 | def editDistance(str1,str2): |
测试
1 | str1 ='cat' |
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) \}$。有如下两种情况:
- 当前字符相等:
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} $
- 当前字符不等:
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次