Levenshtein 距离算法比 O(nm) 更好

Levenshtein距离算法是一种计算两个字符串之间的编辑距离的算法，它用于衡量两个字符串之间的相似度或差异程度。在该算法中，我们需要对两个字符串进行操作，以使它们完全相同，这些操作包括插入、删除和替换字符。然而，Levenshtein距离算法的时间复杂度为O(n*m)，其中n和m分别是两个字符串的长度。

python
def damerau_levenshtein_distance(s1, s2):
    len1 = len(s1)
    len2 = len(s2)
    d = [[0] * (len2 + 1) for _ in range(len1 + 1)]
    for i in range(len1 + 1):
        d[i][0] = i
    for j in range(len2 + 1):
        d[0][j] = j
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            d[i][j] = min(d[i-1][j] + 1,         # 删除操作
                          d[i][j-1] + 1,         # 插入操作
                          d[i-1][j-1] + cost)    # 替换操作
            if i > 1 and j > 1 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]:
                d[i][j] = min(d[i][j], d[i-2][j-2] + cost)  # 交换操作
    return d[len1][len2]
# 测试
s1 = "kitten"
s2 = "sitting"
distance = damerau_levenshtein_distance(s1, s2)
print("Damerau-Levenshtein距离：", distance)