刷题使我快乐，满脸开心.jpg

  • 来源：力扣（LeetCode）
  • 链接：https://leetcode.cn/problems/minimum-cost-to-convert-string-i/
  • 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。

另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。

返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

示例 1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
输出：28
解释：将字符串 "abcd" 转换为字符串 "acbe" ：
- 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。
- 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。
- 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。
- 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。
可以证明这是可能的最小成本。

示例 2：

输入：source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
输出：12
解释：要将字符 'a' 更改为 'b'：
- 将字符 'a' 更改为 'c'，成本为 1 
- 将字符 'c' 更改为 'b'，成本为 2 
产生的总成本是 1 + 2 = 3。
将所有 'a' 更改为 'b'，产生的总成本是 3 * 4 = 12 。

示例 3：

输入：source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
输出：-1
解释：无法将 source 字符串转换为 target 字符串，因为下标 3 处的值无法从 'd' 更改为 'e' 。

提示：

  • 1 <= source.length == target.length <= 105
  • source、target 均由小写英文字母组成
  • 1 <= cost.length== original.length == changed.length <= 2000
  • original[i]、changed[i] 是小写英文字母
  • 1 <= cost[i] <= 10^6
  • original[i] != changed[i]

思路

看似说一大堆，但是其实拆解开来，就是

计算source、target每个位置上不相同字符的转换成本之和
所以计算出来26个小写字母到另一个字母的转换最小成本就可以方便计算了

动态规划

而计算每个字符的转换成本，就是一个常见的动态规划题了：

  • dp[i][j] 含义: 为从i到j转换的成本，为了便于使用，i 和 j 均为该字符与'a'的ASCII码差值
  • 状态转移方程: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
  • 初始化:
    • 相同字符成本则为0，不相同可以先设为一个极大值，这里要小心后续计算时候相加时的数字越界问题
    • 然后可以起三层循环，根据状态方程逐步计算出每两个字母间的最小转换成本

剩下的就简单了。老样子，细节在代码注释

代码

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) int64 {
    // 数组初始化，为了防止数字越界，使用了int64，和 MaxInt32的 极大值
	dp := make([][]int64, 26)
	for i, _ := range dp {
		dp[i] = make([]int64, 26)
		for j, _ := range dp[i] {
			if i != j {
				dp[i][j] = math.MaxInt32
			}
		}
	}

    // 先根据现有成本数组算出一些初始的数据
	for i, _ := range original {
		dp[original[i]-'a'][changed[i]-'a'] = min64(dp[original[i]-'a'][changed[i]-'a'], int64(z))
	}

    // 再根据状态转移方程算出所有可得出的转换成本
	for k, _ := range dp {
		for i, _ := range dp {
			for j, _ := range dp {
				dp[i][j] = min64(dp[i][j], dp[i][k]+dp[k][j])
			}
		}
	}

    // 计算成本部分就没太多要说的了，注意无法转换的判断就好
	totalCost := int64(0)
	sourceBytes := []byte(source)
	targetBytes := []byte(target)
	for i, _ := range sourceBytes {
		if sourceBytes[i] != targetBytes[i] {
			byteCost := dp[sourceBytes[i]-'a'][targetBytes[i]-'a']
			if byteCost == math.MaxInt32 {
				return -1
			} else {
				totalCost += int64(byteCost)
			}
		}
	}
	return totalCost
}

func min64(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}