题解 | #编辑距离(一)#

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        m = len(str1)
        n = len(str2)

        if m * n == 0:
            return m+n
        
        # 构造[m+][n+1]维数组储存数据
        dp = [[0]*(n+1) for _ in range(m+1)]

        # 初始状态赋值
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j

        for i in range(1,m+1):
            for j in range(1,n+1):
                left = dp[i][j-1] + 1  # 对str2删除
                up = dp[i-1][j] + 1    # 对str1删除
                left_up = dp[i-1][j-1] + 1  # 进行替换

                # 如果对应字符串相等，注意str对应的下标需减1
                if str1[i-1]==str2[j-1]:  
                    left_up = left_up - 1
                
                dp[i][j]=min(left,up,left_up)
        
        return dp[m][n]