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

解题思路：

如图

构造如图数组，表示从str1转换为str2消耗的资源；

第1行表示从空串转换为str2消耗的资源

第1列表示从str1转换为串消耗的资源

步骤1：

因为str1[2]=str2[2]，不需要转换，所以消耗dp[3][3]=dp[2][2]

步骤2：

因为str1[1]!=str2[1]，转换路径有三条，分别是：

1、先把str1[0-1]转换为str2[0]，再插入一个str2[1]，消耗为dp[2][1]+ic；

2、先把str1[0]转换为str2[0-1]，再删除原来的str1[1]，消耗为dp[1][2]+dc；

3、先把str1[0]转换为str2[0]，再把str[1]替换为str2[1]，消耗为dp[1][1]+rc；

在这三条路径中取最小值

依此类推

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# min edit cost
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @param ic int整型 insert cost
# @param dc int整型 delete cost
# @param rc int整型 replace cost
# @return int整型
#
class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        length_1 = len(str1)
        length_2 = len(str2)
        res = 0
        dp = [[0 for i in range(length_2 + 1)] for i in range(length_1 + 1)]
        for i in range(length_1 + 1):
            for j in range(length_2 + 1):
                if j == 0:
                    dp[i][0] = i * dc
                elif i == 0:
                    dp[0][j] = j * ic
                elif str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j] + dc,dp[i][j-1] + ic,dp[i-1][j-1] + rc)
        
        print(dp)
        return dp[length_1][length_2]