QA/distance.py

def edit_distance(text1, text2):
    # 初始化矩阵
    m = len(text1) + 1
    n = len(text2) + 1
    dp = [[0 for _ in range(n)] for _ in range(m)]

    # 初始化第一行和第一列
    for i in range(1, m):
        dp[i][0] = i
    for j in range(1, n):
        dp[0][j] = j

    # 计算编辑距离
    for i in range(1, m):
        for j in range(1, n):
            if text1[i-1] == text2[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[-1][-1]