以下是 Python 中实现 Levenshtein 算法的示例代码:

def levenshtein_distance(s1, s2):
    m = len(s1)
    n = len(s2)
    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 s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

该函数接受两个字符串作为参数。它返回这两个字符串之间的 Levenshtein 距离,即将一个字符串转换为另一个字符串所需的最小编辑距离。

该算法使用动态规划的思想。它创建一个二维数组,大小为 (m+1)x(n+1),其中 m 和 n 分别是两个字符串的长度。数组中的每个单元格 dp[i][j] 表示将 s1 的前 i 个字符转换为 s2 的前 j 个字符所需的最小编辑距离。该算法通过填充数组中的所有单元格来计算 Levenshtein 距离。最终返回 dp[m][n]。


原文地址: https://www.cveoy.top/t/topic/nc0d 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录