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

def main():
    A = input()
    B = input()
    m = len(A)
    n = len(B)
    dp = [[1 for i in range(n + 1)] for j in range(m + 1)]
    for i in range(n + 1):
        dp[0][i] = i
    for j in range(m + 1):
        dp[j][0] = j
    # 构造二维动态规划矩阵，设置
    """
    m\n [[0, 1, 2, 3, 4, 5, 6],
         [1, 1, 1, 1, 1, 1, 1],
         [2, 1, 1, 1, 1, 1, 1],
         [3, 1, 1, 1, 1, 1, 1],
         [4, 1, 1, 1, 1, 1, 1],
         [5, 1, 1, 1, 1, 1, 1],
         [6, 1, 1, 1, 1, 1, 1],
         [7, 1, 1, 1, 1, 1, 1]]
    """
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            """
            i-1,j-1  i-1, j
                    \    |
            i, j-1 -  i, j
            
            """
            if A[i - 1] == B[j - 1]:  # 如果两个字符串相同，直接取dp[i-1][j-1]的值
                dp[i][j] = dp[i - 1][j - 1]
            else:  # 如果不相同，则取之前三个方向的最小值并加1
                dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
    print(dp[m][n])


while True:
    try:
        main()
    except:
        break