By

文章目錄

最短编辑距离说的是两个字符串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)

打赏作者

文章目錄