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

def edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    
    # 初始化动态规划表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化边界情况
    for i in range(1, m + 1):
        dp[i][0] = i  # 删除所有字符
    for j in range(1, 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 - 1], dp[i - 1][j], dp[i][j - 1]) + 1  # 替换、删除、插入
            
    # 返回最终结果
    return dp[m][n]

# 读取输入
str1 = input().strip()
str2 = input().strip()

# 输出编辑距离
print(edit_distance(str1, str2))