文章目錄

最短编辑距离说的是两个字符串A和B,求用最少的字符操作将字符串A转化为字符串B。这里所说的字符操作包括
1.删除一个字符
2.插入一个字符
3.将一个字符改为另一个字符

分析:
先比较A和B的第一个字符,分两种情况
1.两个字符相等
此时只需要计算A和B剩下字符的编辑距离
2.两个字符不相等
此时有三种选择,
(1)删除A的第一个字符,之后求A剩下的字符与B的编辑距离
(2)在A中插入B的第一个字符,之后求A与B剩下字符的编辑距离
(3)将A的第一个字符变成B的第一个字符,之后求A剩下的字符与B剩下的字符的编辑距离
之后返回这三种情况的最小值,再加上1,即是A转化为B的最短编辑距离

依照上述方法,很容易写出一个递归方法

1
2
3
4
5
6
7
8
9
10
11
12
def edit_distance(a, b):
if a == '':
return len(b)
if b == '':
return len(a)
if a[0] == b[0]:
return edit_distance(a[1:], b[1:])
else:
return min(edit_distance(a[1:], b), edit_distance(a, b[1:]), edit_distance(a[1:], b[1:])) + 1
A="fxpimu"
B="xwrs"
print edit_distance(A, B)

唯一的缺点是,这种方法太慢了,于是想到用动态规划,此时最好还是从后面考虑,也就是考虑A和B最后一个字符的相等情况,再根据上面的分析计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def edit_distance(a, b):
la = len(a)
lb = len(b)
dp = [[0 for i in xrange(lb + 1)] for j in xrange(la + 1)]
for i in xrange(1, la + 1):
dp[i][0] = i
for j in xrange(1, lb + 1):
dp[0][j] = j
for i in xrange(la):
for j in xrange(lb):
if a[i] == b[j]:
dp[i + 1][j + 1] = dp[i][j]
else:
dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
return dp[la][lb]

A="fxpimu"
B="xwrs"
print edit_distance(A, B)

文章目錄