编辑距离与动态规划算法

编辑距离与动态规划

编辑距离

这是Leetcode上面中高等难度的题目，在计算文本相似性的时候，经常会用到编辑距离。它指的是两个字串之间，由一个转成另一个所需的最少的编辑操作的次数。通常来说，编辑距离越小，说明两个文本的相似性越大，具体的编辑的操作主要分为三种：

1. 插入：将一个字符，插入某个字符串
2. 删除：将字符串中的某个字符删除
3. 替换：将字符串中的某个字符替换为另外一个字符

例子

1. 把batyu变成beatyu，需要插入字符e，这就是一次编辑操作
2. beatyu变为beaty，需要删除字符u，一次操作
3. apple变成appel，需要两次操作

dhsfka fdshakjfhl

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    if m == 0:
        return n
    if n == 0:
        return m

    # 建立（m+1）*(n+1)的表格，s1是横向，s2是纵向
    edit = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        edit[i][0] = i
    for j in range(1, n + 1):
        edit[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                diff = 0
            else:
                diff = 1
            edit[i][j] = min(edit[i - 1][j - 1] + diff, edit[i - 1][j] + 1, edit[i][j - 1] + 1)

    return edit[m][n]

print(edit_distance('好的伤口恢复了', '浑善达克距离罚款'))