题解 | #计算字符串的编辑距离#暴力递归~备忘录~动态规划

#暴力递归

#计算s1[0:i+1]和s2[0:j+1]的最小编辑距离
def minDistance(s1,i,s2,j):
    #base case
    #（如果两个字符串任意一个为空的情况,最小操作为另一字符串的长度）
    if i==-1: return j+1
    if j==-1: return i+1

    """
    字符串编辑处理，从后往前如：
    插入：是对s2字符串尾部插入一个字符
    删除：是对s1字符串尾部删除一个字符
    替换：是对s1字符串尾部变化一个字符
    """
    if s1[i]==s2[j]:
        #如果一致，什么都不做比较，往前跳一位
        return minDistance(s1,i-1,s2,j-1)
    else:
        return min(
            minDistance(s1,i,s2,j-1)+1,#插入
            minDistance(s1,i-1,s2,j)+1,#删除
            minDistance(s1,i-1,s2,j-1)+1 #替换
        )

while True:
    try:
        s1,s2=input(),input()
        #取s1和s2最大索引
        i,j=len(s1)-1,len(s2)-1
        print(minDistance(s1,i,s2,j))
    except:
        break

#动态规划（备忘录,递归）
def minDistance(s1,i,s2,j,memo):
    #base case 
    if i==-1: return j+1
    if j==-1: return i+1
    #提取备忘录，避免重叠子问题
    if memo[i][j]!=-1:
        return memo[i][j]
    #状态转移方程，存储备忘录
    if s1[j]==s2[i]:
        memo[i][j]=minDistance(s1,i-1,s2,j-1,memo)
    else:
        memo[i][j]=min(
            minDistance(s1,i,s2,j-1,memo)+1,#插入
            minDistance(s1,i-1,s2,j,memo)+1,#删除
            minDistance(s1,i-1,s2,j-1,memo)+1 #替换
        )
    return memo[i][j]
while True:
    try:
        s1,s2=input(),input()
        m,n=len(s1),len(s2)
        #初筛化备忘录，注意行列对应
        memo=[[-1]*m for _ in range(n)]
        #s1为横坐标对应n列，s2为纵坐标对应m行n
        print(minDistance(s1,n-1,s2,m-1,memo))
    except:
        break

# 动态规划（迭代）
while True:
    try:
        s1, s2 = input(), input()
        n, m = len(s1), len(s2)

        # 任意字符串为空的情况下，最小操作次数为另一字符串长度
        if m * n == 0:
            print(m + n)
        # dp二维数组
        dp = [[-1] * (m + 1) for _ in range(n + 1)]
        """
        边界状态初始化
        (相当于其中一个字符串为空，最小操作次数为另一字符串长度一样)
        """
        for i in range(n + 1):
            dp[i][0] = i
        for j in range(m + 1):
            dp[0][j] = j
        # 计算所有dp值
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = dp[i - 1][j]+1
                right = dp[i][j - 1]+1
                left_down = dp[i - 1][j - 1]
                if s1[i - 1] != s2[j - 1]:
                    left_down += 1
                dp[i][j] = min(left, right, left_down)
        print(dp[n][m])
    except:
        break