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

str1 = input()
str2 = input()
length_1 = len(str1)
length_2 = len(str2)
# 创建DP数组,考虑字符可能为空,外层是行，内层是列
dp = [[0 for i in range(length_1 + 1)] for j in range(length_2 + 1)]

# 初始化dp数组
for i in range(length_1 + 1):
    dp[0][i] = i
for j in range(length_2 + 1):
    dp[j][0] = j

# 遍历dp数组，先遍历行，再遍历列
for i in range(1, length_2 + 1):
    for j in range(1, length_1 + 1):

        if str2[i - 1] == str1[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]

        else:
            dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1


print(dp[length_2][length_1])