题目

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

解题思路

我们可以将 26 个小写英文字母看作图中的 26 个节点。题目给出的 original 到 changed 的转换以及对应的 cost，就是图中节点之间的有向边及其权重。

我们的目标是求出将 source 中的每一个字符转换为 target 中对应字符的最小成本总和。

由于可能存在中间转换（例如 a -> b -> c 的成本可能比直接 a -> c 更低），这实际上是求图中任意两点之间的最短路径。

考虑到节点的数量非常少（只有 26 个小写字母），我们可以使用 Floyd-Warshall 算法。

节点数 ($V$)：26
Floyd-Warshall 时间复杂度：$O(V^3)$。对于 $V=26$，$26^3 = 17576$，计算量极小，非常高效。
Dijkstra 算法：也可以对每个字符跑一遍 Dijkstra，但写起来比 Floyd 麻烦，且在这个数据规模下优势不明显。

初始化图 (邻接矩阵)：
- 创建一个 $26 \times 26$ 的二维数组 dist，用来存储字符 $i$ 到字符 $j$ 的最小成本。
- 初始化 dist[i][i] = 0 (自己转自己成本为0)。
- 初始化 dist[i][j] = \infty (表示尚未联通)。
构建初始边：
- 遍历输入的 original, changed, cost 数组。
- 对于每一组转换 $(u, v, w)$，更新 dist[u][v] = min(dist[u][v], w)。
- 注意：题目可能给出多条相同的转换规则但成本不同，我们只保留成本最小的那条。
计算最短路径 (Floyd-Warshall)：
- 使用三层循环遍历所有中间节点 $k$，起点 $i$，终点 $j$。
- 状态转移方程：$$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$$
计算最终总成本：
- 初始化 total_cost = 0。
- 遍历 source 和 target 字符串的每一个位置 $i$。
- 获取 source[i] 对应的索引 $u$ 和 target[i] 对应的索引 $v$。
- 如果 $u == v$，无需转换，跳过。
- 如果 dist[u][v] 仍为 $\infty$，说明无法转换，直接返回 -1。
- 否则，total_cost += dist[u][v]。
返回结果。

复杂度分析

时间复杂度：$O(V^3 + m + n)$
- $V^3$ 是 Floyd 算法部分 ($26^3$)，是常数级。
- $m$ 是 cost 数组的长度 (构建图)。
- $n$ 是 source 字符串的长度 (计算总成本)。
- 总体来看，这是一个线性时间复杂度的解法。
空间复杂度：$O(V^2)$
- 只需要一个 $26 \times 26$ 的矩阵存储距离。

具体代码

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) int64 {
	// 定义一个足够大的数代表无穷大
	// 路径最大成本约为 26 * 10^6，用 int64 最大值的一半足以防止加法溢出，
	// 或者简单地用 math.MaxInt64 配合 if 判断
	const inf = math.MaxInt64

	// 1. 初始化距离矩阵 (26x26)
	// dist[i][j] 表示字符 i 到字符 j 的最小成本
	var dist [26][26]int64
	for i := 0; i < 26; i++ {
		for j := 0; j < 26; j++ {
			if i == j {
				dist[i][j] = 0
			} else {
				dist[i][j] = inf
			}
		}
	}

	// 2. 填充初始边
	// 注意：可能存在多条相同的边，取成本最小的
	for i, c := range cost {
		u := original[i] - 'a'
		v := changed[i] - 'a'
		if int64(c) < dist[u][v] {
			dist[u][v] = int64(c)
		}
	}

	// 3. Floyd-Warshall 算法计算任意两点间的最短路径
	// k: 中间节点, i: 起点, j: 终点
	for k := 0; k < 26; k++ {
		for i := 0; i < 26; i++ {
			// 如果起点到中间点都不可达，直接跳过（剪枝优化）
			if dist[i][k] == inf {
				continue
			}
			for j := 0; j < 26; j++ {
				// 状态转移方程：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
				if dist[k][j] != inf {
					newDist := dist[i][k] + dist[k][j]
					if newDist < dist[i][j] {
						dist[i][j] = newDist
					}
				}
			}
		}
	}

	// 4. 计算 source 到 target 的总成本
	var totalCost int64 = 0
	for i := 0; i < len(source); i++ {
		u := source[i] - 'a'
		v := target[i] - 'a'

		// 如果无法从 u 转换到 v，返回 -1
		if dist[u][v] == inf {
			return -1
		}
		totalCost += dist[u][v]
	}

	return totalCost
}

2976. 转换字符串的最小成本 I

beautifulremi

题目

解题思路

复杂度分析

具体代码