Description

对于两个字符串A和B,我们需要进行插入、删除和修改操作将A串变为B串,定义c0,c1,c2分别为三种操作的代价,请设计一个高效算法,求出将A串变为B串所需要的最少代价。

给定两个字符串AB,及它们的长度和三种操作代价,请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300,且三种代价值均小于等于100。

测试样例:

"abc",3,"adc",3,5,3,100
返回:8

Solutions

1. DP

# -*- coding:utf-8 -*-
# Time: O(mn)
# Space: O(mn)
class MinCost:
    def findMinCost(self, word1, n, word2, m, c0, c1, c2):
        # write code here
        n1, n2 = len(word1), len(word2)
        dp = [[0 for _ in range(n2 + 1)] for _ in range(n1 + 1)]
        dp[0][0] = 0
        for i in range(1, n1 + 1):
            dp[i][0] = dp[i - 1][0] + c1
        for i in range(1, n2 + 1):
            dp[0][i] = dp[0][i - 1] + c0
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j] + c1, dp[i][j - 1] + c0)
                else:
                    dp[i][j] = min(dp[i - 1][j - 1] + c2, dp[i - 1][j] + c1, dp[i][j - 1] + c0)
        return dp[n1][n2]

References

  1. 12.9 最优编辑