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

#levenshtein距离问题，使用动态规划解决
#前提定义：
#dp[i][j]表示A[:i]到B[:j]的编辑距离

#情况分析：
#如果有一个为空，则距离为另一个字符串长度,这一点在本题中不需考虑，因为限定字符串长度大于0
#否则判断A[i]是否等于B[j]
#如果相等，则dp[i][j]=dp[i-1][j-1],因为最后一位相同，不需要参与编辑
#如果不等，就看看走三条路哪条路近
#dp[i][j]=min(
    #dp[i-1][j]+1, 把A[i]删掉需要1次操作，剩下就是dp[i-1][j]
    #dp[i][j-1]+1, 把B[j]删掉需要1次操作，剩下就是dp[i][j-1]
    #dp[i-1][j-1]+1, 把A[i]替换为B[j]需要1次操作，剩下就是dp[i-1][j-1]
    #)

'''
def dp(i,j):
    if i==0 or j==0:
        return max(i,j)
    else:
        if A[i]==B[j]:
            return dp(i-1,j-1)
        else:
            return min(
                dp(i-1,j)+1,
                dp(i,j-1)+1,
                dp(i-1,j-1)+1
            )
A=input()
B=input()
print(dp(len(A)-1,len(B)-1))
'''
#上面使用递归实现要超时，下面使用打表的方式实现


A=input()
B=input()
dp=[[0 for j in range(len(B)+1)] for i in range(len(A)+1)]#建表
#第一行
for i in range(len(B)+1):
    dp[0][i]=i

#第一列
for i in range(len(A)+1):
    dp[i][0]=i

#其他
for i in range(1,len(A)+1):
    for j in range(1,len(B)+1):
        if A[i-1]==B[j-1]:
            dp[i][j]=dp[i-1][j-1]
        else:
            dp[i][j]=min(
                dp[i-1][j]+1,
                dp[i][j-1]+1,
                dp[i-1][j-1]+1
            )
print(dp[len(A)][len(B)])