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

写个 二维数组方式实现的编辑距离。 对于一维数组的改进方式 来简化空间复杂度， 我不是很能理解。 所以我对这道题目的把握更多是理解掌握二维数组的动态规划过程。 需要的话 会回来更新 对一维数组的使用

class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        # write code here
        # minimum cost 
        n= len(str1)
        m=len(str2)
        
        #consider null case
        if n==0 and m!=0:
            # insert in str1 to be str2
            return m*ic 
        if m==0 and n!=0:
            #delete from str1 to be null
            return dc*n
        # initialize two dimensional array
        DP= [[0]*(m+1) for _ in range(n+1)]
        print('dp1',DP)
        #fill in edge case 
        for i in range(n+1):
            DP[i][0]=i*dc # str2 is null, then we ned delete from str1 with i times insertion, couning as dc
        for j in range(m+1):
            DP[0][j]=j*ic # str1 is null then make it to be as str2[:j] then insert 
        print('dp2',DP)
        
        # calculate DP[i][j] based on dynamic equation
        #DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+ int(str1[i]!=str2[j]))
        for i in range(1,n+1):
            for j in range(1,m+1):
                left=DP[i-1][j]+1*dc # delete from str1, 1 means one operation
                down=DP[i][j-1]+1*ic # insert into str1 1 means one operation like insert/delete once
                left_down=DP[i-1][j-1] # 
                if str1[i-1] != str2[j-1]:
                    # 这里 条件 index 是 i-1, j-1 是因为DP 比实际字串多一行和一列。 理解时候理解为对角上的变换
                    # 比如 你已经 填了 所有边界条件，并且 推出 DP[1][1] 代价为 X， 你想知道 DP[2][2] 代表的代价
                    #值是多少  字符串1 是HOR， 字符串2 是RO。 所以 DP[1][1] 代表从字符串1 的前1个字符就是H 
                    #编辑到字符串2 的前1 个字符就是 R 的代价是X， 问的是从字符串的前2个字符 HO 编辑到 字符串的前
                    # 2 个字符 RO 的代价是多少。我们可以列一个 二维的 DP 列表 考虑空字符情况和 各有1个字符等等 
                    #所有可能长度的组合是一个二维的数组列表。 DP[2][2] 可以由 DP[2][1] 加操作得到 就是 HO 先编辑成
                    # R 然后 只要插入O 就是 RO 所以代价是 DP[2][1]+1, 或者 从 DP[1][2] 就是H 先变成 RO 再 因为 
                    #两个字符串的第二个字符相等 所以DP[2][2]不用再编辑这样就是 代价值DP[1][1]==DP[2][2]. 
                    # 这里条件判断时候。I,J 是2 但是字符是从INDEX 0 开始count。所以条件是str1[i-1] != str2[j-1]:?  
                    # 如果 两个字符的第二个字符不相等 那么我们需要进行替换的操作比如 字符串前两个字符不是HO 而是 HY
                    # 这样编辑成 RO 时候 我们已经知道H 到R 的代价 那么需要变成RO 就是 替换 Y 变成O 
                    # 这样我们就需要 在DP[1][1] 上加上 替换的代价值就是 我们下面做的 
                    left_down+=1*rc # if the letter is not the same then we need to replace 
                DP[i][j]= min(left,down,left_down)
        return DP[n][m]