编辑距离(二)

# -*- coding: utf-8 -*-

#
# 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:
    """
    题目：
        https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4?tpId=117&&tqId=37801&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
    算法：
        设dp[i][j]表示将字符串str1的前i个字符编辑为字符串str2的前j个字符所需的最小代价
        ic、dc、rc分别代表插入、删除和替换一个字符的代价，m, n分别为str1，str2的长度
        初始化：
            dp[0][0] = 0 # 空字符串 + 空字符串 = 空字符串，无需编辑
        状态转移方程：
            dp[i][0] = i * dc
            dp[0][j] = j * ic
            若str1[i-1] == str2[j-1]：
                dp[i][j] = dp[i - 1][j - 1]
            否则：
                dp[i][j] = min(dp[i][j-1] + ic,  # 对str1插入一个字符，进行匹配，匹配后，str2长度-1
                                dp[i-1][j] + dc # 删除字符str1[i-1]，进行匹配，str1长度-1
                                dp[i - 1][j - 1] + rc) # 替换str1[i - 1]为str2[j - 1]进行匹配，两者长度均-1
        返回值：
            dp[m][n]
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def minEditCost(self, str1, str2, ic, dc, rc):
        m, n = len(str1), len(str2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):  # str2长度为0，只能删除
            dp[i][0] = i * dc

        for j in range(1, n + 1):  # str1长度为0，只能插入
            dp[0][j] = j * ic

        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:
                    dp[i][j] = min(dp[i][j - 1] + ic,
                                   dp[i - 1][j] + dc,
                                   dp[i - 1][j - 1] + rc)

        return dp[m][n]


if __name__ == '__main__':
    s = Solution()

    str1, str2, ic, dc, rc = "abc", "adc", 5, 3, 2

    # str1, str2, ic, dc, rc = "abc", "adc", 5, 3, 100

    res = s.minEditCost(str1, str2, ic, dc, rc)
    print res