最小编辑距离python

最小编辑距离（Levenshtein距离）是一种衡量两个字符串之间差异程度的度量方法。在Python中，你可以使用动态规划的方法来实现最小编辑距离。

下面是一个基本的实现示例：

def min_edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i

    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1

    return dp[m][n]

你可以调用这个函数来计算两个字符串之间的最小编辑距离。例如：

word1 = "kitten"
word2 = "sitting"
distance = min_edit_distance(word1, word2)
print(distance)  # 输出结果为 3

这个示例中，"kitten" 和 "sitting"之间的最小编辑距离是3，表示需要进行3次插入、删除或替换操作才能将一个字符串转化为另一个字符串。