计算字符串的编辑距离

'''
会爆内存，易理解（递归 + 记忆化搜索）

思路：dfs(i, j)表示s1的前i个字符匹配s2的前j个字符最少需要几次操作。
考虑字符串s1,s2的第i位和第j位，有相同和不同两种情况。
如果相同，则匹配s1和s2的下一位，即dfs(i, j) = dfs(i + 1, j + 1)
如果不同，则有三种操作（s1固定，只对s2操作）：
删除s2的当前位，匹配第j + 1位：dfs(i, j) -> dfs(i, j + 1) + 1
s2的当前位添加一个元素：dfs(i, j) -> dfs(i + 1, j) + 1
修改s2当前位元素：dfs(i, j) -> dfs(i + 1, j + 1) + 1
这三种操作取最小值，即dfs(i, j) = min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1)) + 1
中间涉及重复计算，因此采用记忆化搜索剪枝 from functools import lru_cache
s1 = input()
s2 = input()

@lru_cache(None)
def dfs(i, j):
    # 边界情况，如果其中一个匹配完了，剩余的都要删除
    if j == len(s2)&nbs***bsp;i == len(s1):
        return max(len(s1) - i, len(s2) - j)
    if s1[i] == s2[j]:
        return dfs(i + 1, j + 1)
    return min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1)) + 1
print(dfs(0, 0))
'''
# 手动定义cache数组 s1 = input()
s2 = input()
cache = [[-1 for _ in range(len(s2) + 1)] for __ in range(len(s1) + 1)]
def dfs(i, j):
    # 如果前面访问过了
    if cache[i][j] != -1:
        return cache[i][j] # 边界情况，如果其中一个匹配完了，剩余的都要删除     if j == len(s2) or i == len(s1):
        cache[i][j] = max(len(s1) - i, len(s2) - j)
        return cache[i][j]
    # s1第i位和s2第j位相同，无需操作，匹配下一位
    if s1[i] == s2[j]:
        cache[i][j] = dfs(i + 1, j + 1)
        return cache[i][j]
    # 否则，三种操作中选最小的
    cache[i][j] = min(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1)) + 1
    return cache[i][j]
print(dfs(0, 0)) 

while True:
    try:
        s1, s2 = input(), input()
        n1, n2 = len(s1), len(s2)
        # 初始化数组dp，赋值
        dp = [[0] * (n2+1) for _ in range(n1+1)]
        
        # 初始化边界，赋值
        for i in range(1, n2+1):
            dp[0][i] = i
        for i in range(1, n1+1):
            dp[i][0] = i
            
        # 遍历两个字符串
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] #左上角元素
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 #左，上，左上，三个数中的最小值
        print(dp[n1][n2])
    except:
        break

## 动态规划
str1 = input()
str2 = input()
m = len(str1)
n = len(str2)
         
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
    
for i in range(1,m+1):
    for j in range(1,n+1):
        if str1[i-1] == str2[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:
        a = input()
        b = input()
        la = len(a)
        lb = len(b)
        dp = [[0 for i in range(lb+1)] for j in range(la+1)]
        for i in range(la+1):
            dp[i][0] = i
        for j in range(lb+1):
            dp[0][j] = j
        for i in range(1, la+1):
            for j in range(1, lb+1):
                if a[i-1] == b[j-1]:
                    dp[i][j] = min(dp[i-1][j-1]-1, dp[i-1][j], dp[i][j-1])+1
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
        print(dp[la][lb])
    except:
        break

while True:
    try:
        strA,strB = input(),input()
        la,lb = len(strA)+1,len(strB)+1
        dp = [[i for i in range(lb)] for j in range(2)]
        for i in range(1,la):
            dp[1][0]=i        
            for j in range(1,lb):
                dp[1][j] = min(dp[0][j-1]+(1 if strA[i-1]!=strB[j-1] else 0),dp[1][j-1]+1,dp[0][j]+1)
            dp[0]=dp[1][:]
        print(dp[0][-1])
    except:
        break

'''
递归
- 大量的重复计算，导致超时
- 优化：Memorization（二维数组）， 动态规划
'''


def distance(a, b):
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)

    cos = 0
    if a[-1] != b[-1]:
        cos = 1

    lev1 = distance(a[:len(a) - 1], b) + 1
    lev2 = distance(a, b[:len(b) - 1]) + 1
    lev3 = distance(a[:len(a) - 1], b[:len(b) - 1]) + cos

    return min(lev1, lev2, lev3)

'''
动态规划：
 - 自底向上，避免大量重复运算
 - 从状态转移抽象出状态转移方程
   1. 如果StringA[i] == StringB[j], 那么dp[i][j] = dp[i-1][j-1]
   2. 否则，dp[i][j] == min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1, 对应于对String B执行insert, delete, replace操作
 - 测试
   1. 字符串为空（边界）
   2. 正常字符串
'''


def dynamic(a, b):

    dp = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]

    # 构造初始解，即某字符串为空的情况
    for i in range(1, len(a) + 1):
        dp[i][0] = i
    for j in range(1, len(b) + 1):
        dp[0][j] = j

    # 状态转移方程，注意边界！
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j]
            else:
                dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1

    return dp[-1][-1]


if __name__ == '__main__':
    while True:
        try:
            a = input()
            b = input()
            res = dynamic(a, b)
            # res = distance(a, b)
            print(res)
        except:
            break