2019年3月

Levenshtein distance

概念

莱文斯坦距离Levenshtein distance)是将一个单词更改为另一个单词所需的最少编辑操作次数。莱文斯坦距离允许的编辑操作包括单个字符的 替换/插入/删除。

实例

给定字符串kittensitting,前者可以通过以下步骤变换成后者:

  1. kitten → sitten (将k替换为s)

  2. sitten → sittin (将e替换为i)

  3. sittin → sitting (在尾部插入g)

无法通过更少的步骤完成替换,故两者的莱文斯坦距离为3

算法

请输入图片描述

实现

def levenshteinDistance(s1, s2):
    m = len(s1)
    n = len(s2)
    dt = []

    # 初始化距离表
    for i in range(m+1):
        temp = []
        for j in range(n+1):
            if i==0:
                temp.append(j)
            elif j==0:
                temp.append(i)
            else:
                temp.append(0)
        dt.append(temp)

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