题解 | 计算字符串的编辑距离

def levenshtein_distance(str1, str2):
    m, n = len(str1), len(str2)
    # 初始化动态规划表
    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 str1[i - 1] == str2[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]


# 输入处理
str1 = input().strip()
str2 = input().strip()

# 计算编辑距离
result = levenshtein_distance(str1, str2)
print(result)