动态规划 | HJ52 计算字符串的编辑距离

while True:
    try:
        s1 = input()
        s2 = input()
        if len(s2) < len(s1):
            s1, s2 = s2, s1 
        cnt = 0
        dp = [[-1]*(len(s2)+1) for _ in range(len(s1)+1)]
        for i in range(len(s1)+1):
            dp[i][0] = i
        for j in range(len(s2)+1):
            dp[0][j] = j
        for i in range(1, len(s1)+1):
            for j in range(1, len(s2)+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # 分别代表s2添加(i-1后s1少1字符，s2相对多1字符)、删除、替换
                    last = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                    dp[i][j] = 1 + last
        print(dp[-1][-1])
    except:
        break

用时：2h