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

'''
行数为len(oppa)+1,列数为len(apple)+1,加1是因为要考虑 空字符串

第0行中每列值含义：（绿色格子表格）
以第0行第2列为例，表示由 空字符串 变成 'ap' 需要的编辑次数，显然在空字符串中执行两次添加操作即可，所以填2，第0行其他列以此类推

第0列每行的含义：
以第2行第0列为例，表示由 字符串'op' 变成 空字符串 需要的编辑次数，显然对'op'执行两次删除操作即可，所以填2，第0列其他行以此类推

其他空格处含义:
以第2行第4列为例，其代表'op'变'appl'操作
相对于左边空格的'op'变'app'操作上再执行一次添加'l'操作
相对于上边空格的'o'变'appl'操作上再执行一次删除'p'操作
相对于左上角空格的'o'变'app'操作上再执行一次替换'p'变'l'操作

'''

str1=input()# 等价于'oppa'
str2=input()# 等价于'apple'

# 构建bp表格,str1往str2编辑
bp=[[x for x in range(len(str2)+1)] for y in range(len(str1)+1)]
# 现在bp表格中每一行的值为0、1、...len(str2)，其中第0行所有值是正确的
# 现在要改变第0列的值为0、1、...len(str1)
for w in range(1,len(str1)):
    bp[w][0]=bp[w-1][0]+1

# 由于第0行和第0列均更新完成，现在要更新其他空格中的值
for j in range(1,len(str1)+1):# 从第表格中的第1行第1列，即bp[1][1]处开始，遍历每一行str1:'oppa'
    for k in range(1,len(str2)+1):# 从第表格中的第1行第1列，即bp[1][1]处开始，遍历每一列
        if str1[j-1]==str2[k-1]:# 当最后一个字符相同时，等价于没有改字符
            bp[j][k]=bp[j-1][k-1]
        elif str1[j-1]!=str2[k-1]:#当最后一个字符不相同时，比较左、上、左上三个位置的值，+1后的找最小值，即最小编辑距离
            add=bp[j][k-1]+1
            delete=bp[j-1][k]+1
            replace=bp[j-1][k-1]+1
            bp[j][k]=min(add, delete, replace)

print(bp[len(str1)][len(str2)])