python最短编辑距离

Python中可以使用动态规划算法来求解最短编辑距离。最短编辑距离指的是将一个字符串转换为另一个字符串所需的最少编辑操作次数。

下面是一个实现最短编辑距离的示例代码：

def min_edit_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] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    # 返回最后一个元素，即最短编辑距离
    return dp[m][n]

# 测试示例
s1 = "kitten"
s2 = "sitting"
distance = min_edit_distance(s1, s2)
print("最短编辑距离为:", distance)

以上代码将输出最短编辑距离为 3，表示将字符串 "kitten" 转换为 "sitting" 需要进行3次编辑操作。