转换字符串的最小成本 I

难度: Medium

给你两个下标从 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 <= 10⁵
source、target 均由小写英文字母组成
1 <= cost.length== original.length == changed.length <= 2000
original[i]、changed[i] 是小写英文字母
1 <= cost[i] <= 10⁶
original[i] != changed[i]

Submission

运行时间: 304 ms

内存: 17.9 MB

class Solution:
	def minimumCost(self, source, target, original, changed, cost):
		mat = [[float('inf')] * 26 for _ in range(26)]
		for i in range(26):
			mat[i][i] = 0
		map0 = [{} for _ in range(26)]
		for i in range(len(cost)):
			u = ord(original[i]) - 97
			v = ord(changed[i]) - 97
			w = cost[i]
			map0[u][v] = min(map0[u].get(v, float('inf')), w)
		for i in range(26):
			self.dfs(map0, i, mat)
		ans = 0
		for i in range(len(source)):
			ans += mat[ord(source[i]) - 97][ord(target[i]) - 97]
		return -1 if ans == float('inf') else ans
	
	def dfs(self, map0, h, mat):
		q = [[0, h]]
		while q:
			d, u = heapq.heappop(q)
			if d != mat[h][u]:
				continue
			for v in map0[u]:
				cur = map0[u][v] + d
				if cur < mat[h][v]:
					mat[h][v] = cur
					heapq.heappush(q, [cur, v])

Explain

题解使用了图的最短路径算法（Floyd-Warshall 变体）来计算字符转换的最小成本。首先，建立一个 26x26 的矩阵 mat，用于表示从一个字符到另一个字符的最小转换成本。矩阵中每个元素初始化为无穷大，除了对角线元素（即自身到自身的转换成本为0）。随后，使用一个数组 map0 来存储每个字符对的最小转换成本。接着使用一个深度优先搜索（DFS）结合优先队列（最小堆）来计算任何字符到任何字符的最短路径。最后，遍历 source 字符串和 target 字符串，利用预计算的最短路径成本矩阵来计算整体的最小转换成本。如果任何字符的转换成本为无穷大，表明转换不可能完成，返回 -1。

时间复杂度: O(k + 26^2 * log(26) + n)

空间复杂度: O(k + 26^2)

class Solution:
    def minimumCost(self, source, target, original, changed, cost):
        mat = [[float('inf')] * 26 for _ in range(26)]  # 创建成本矩阵
        for i in range(26):
            mat[i][i] = 0  # 初始化自转换成本为0
        map0 = [{} for _ in range(26)]  # 创建映射关系表
        for i in range(len(cost)):
            u = ord(original[i]) - 97
            v = ord(changed[i]) - 97
            w = cost[i]
            map0[u][v] = min(map0[u].get(v, float('inf')), w)  # 存储最小成本
        for i in range(26):
            self.dfs(map0, i, mat)  # 计算最短路径
        ans = 0
        for i in range(len(source)):
            ans += mat[ord(source[i]) - 97][ord(target[i]) - 97]  # 累计总成本
        return -1 if ans == float('inf') else ans  # 检查是否有不可能的转换

    def dfs(self, map0, h, mat):
        q = [[0, h]]  # 使用优先队列
        while q:
            d, u = heapq.heappop(q)
            if d != mat[h][u]:
                continue
            for v in map0[u]:
                cur = map0[u][v] + d
                if cur < mat[h][v]:
                    mat[h][v] = cur
                    heapq.heappush(q, [cur, v])  # 更新路径成本并继续搜索

Explore

在处理字符转换成本时，选择使用图的最短路径算法是因为这些转换可以被视为图中的边，其中每个字符代表一个顶点，转换成本代表从一个顶点到另一个顶点的边的权重。使用最短路径算法可以有效地计算任何两个字符之间的最小转换成本，即使存在多条路径（即多种转换方式）。特别是Floyd-Warshall变体的算法能够处理所有顶点对的最短路径问题，适合这里的全局最小成本计算需求。

在存在多个不同成本的相同字符转换规则的情况下，我们需要选择成本最低的转换规则。在构建成本映射时，通过检查每个字符对应的转换规则，使用字典来更新每个字符对的最低转换成本。如果新的转换成本低于字典中已存储的成本，则用新的成本替换原有成本。这确保了任何字符转换都使用可能的最小成本。

DFS和最小堆结合使用的主要目的是高效地搜索和更新图中的最短路径。在这种方法中，DFS用于深度优先遍历图的顶点，而最小堆（优先队列）用于始终首先处理当前最小成本的路径。这种结合提高了搜索效率，因为最小堆确保我们总是首先探索当前已知的最短路径，从而减少了不必要的路径探索和更新，加快了最短路径的收敛速度。

在使用优先队列时，可能会有多个相同顶点但成本不同的元素被加入队列。当一个顶点的最短路径成本在队列中等待时被更新为一个更小的值，旧的更高成本的元素仍然存在于队列中。出队时检查元素的成本是否与矩阵中记录的成本一致，是为了确保我们不处理那些已经被更优路径更新过的顶点的过时成本，从而保持算法的正确性和效率。