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

# 思路：
# 对于两个单字符a,b，考虑是否相同：
# 1.相同，则不需要改变，编辑距离为0
# 2.不相同，需要改变。方法是替换，编辑距离为1
# 对于两个字符串a,b，考虑切片a[:i]段，b[:j]段是否相同。先看末位
# 1.相同 不需要改变。编辑距离应等同于都去掉该位的字符串a[:i],b[:j]的编辑距离，记为dp[i][j] = dp[i-1][j-1]
# 2.不相同 需要改变此位。要使a[i]==b[j]，可以：
# 2.1替换a[i]为b[j]，之后需要将a[:i-1]段转换为b[:j-1]段，故编辑距离为dp[i-1][j-1]+1
# 2.2删除a[i]，之后需要将a[:i-1]段转换为b[:j]段，故编辑距离为dp[i-1][j]+1
# 2.3添加b[j]在a[i]之后，之后需要将a[:i]段转换为b[:j-1]段，故编辑距离为dp[i][j-1]+1
# 上述操作后即可实现a[:i]段==b[:j]。a[:i]段转换为b[:j]的最小次数也应当是上述式子的最小值


text1 = input()
text2 = input()

dp = [[0 for j in range(len(text2)+1)] for i in range(len(text1)+1)]

# 构建dp
for i in range(1,len(text1)+1):
    dp[i][0] = i
for j in range(1,len(text2)+1):
    dp[0][j] = j
# 设置初值
# for tmp in dp:
#     print(tmp)

# dp
for i in range(1,len(text1)+1):
    for j in range(1, len(text2)+1):
        if text1[i-1] == text2[j-1]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)

print(dp[len(text1)][len(text2)])