Python求字符串编辑距离 ？

字符串编辑距离，也称为Levenshtein距离，是一个衡量两个字符串之间差异的度量。这个距离被定义为将一个字符串转换为另一个字符串所需的最少单字符编辑操作（插入、删除或替换）的数量。

在Python中，你可以使用动态规划来计算两个字符串之间的Levenshtein距离。下面是一个简单的实现：

def levenshtein_distance(s1, s2):
    if len(s1) < len(s2):
        return levenshtein_distance(s2, s1)

    if len(s2) == 0:
        return len(s1)

    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row

    return previous_row[-1]

# 示例
s1 = "kitten"
s2 = "sitting"
print(levenshtein_distance(s1, s2))  # 输出：3

这个实现使用了动态规划来构建一个矩阵，其中每个单元格dp[i][j]表示s1的前i个字符和s2的前j个字符之间的Levenshtein距离。然后，我们遍历s1和s2的每个字符，并根据需要更新dp矩阵。最后，dp[len(s1)][len(s2)]就是s1和s2之间的Levenshtein距离。