LeetCode 题解工作台
转换字符串的最小成本 I
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。 另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 ch…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·string
答案摘要
根据题目描述，我们可以将每个字母看作一个节点，每对字母的转换成本看作一条有向边。那么我们先初始化一个 $26 \times 26$ 的二维数组 ，其中 表示字母 转换成字母 的最小成本。初始时 $g[i][j] = \infty$，如果 $i = j$，那么 $g[i][j] = 0$。 然后我们遍历数组 , 和 ，对于每个下标 ，我们将 转换成 的成本 更新到 中，取最小值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你两个下标从 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 <= 105source、target均由小写英文字母组成1 <= cost.length== original.length == changed.length <= 2000original[i]、changed[i]是小写英文字母1 <= cost[i] <= 106original[i] != changed[i]
解题思路
方法一：Floyd 算法
根据题目描述，我们可以将每个字母看作一个节点，每对字母的转换成本看作一条有向边。那么我们先初始化一个 的二维数组 ，其中 表示字母 转换成字母 的最小成本。初始时 ，如果 ，那么 。
然后我们遍历数组 , 和 ，对于每个下标 ，我们将 转换成 的成本 更新到 中，取最小值。
接下来，我们使用 Floyd 算法计算出 中任意两个节点之间的最小成本。最后，我们遍历字符串 和 ，如果 ，并且 ，那么说明无法完成转换，返回 。否则，我们将 累加到答案中。
遍历结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度；而 是字母表的大小，即 。
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: List[str],
changed: List[str],
cost: List[int],
) -> int:
g = [[inf] * 26 for _ in range(26)]
for i in range(26):
g[i][i] = 0
for x, y, z in zip(original, changed, cost):
x = ord(x) - ord('a')
y = ord(y) - ord('a')
g[x][y] = min(g[x][y], z)
for k in range(26):
for i in range(26):
for j in range(26):
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = 0
for a, b in zip(source, target):
if a != b:
x, y = ord(a) - ord('a'), ord(b) - ord('a')
if g[x][y] >= inf:
return -1
ans += g[x][y]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m + n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Tests the candidate's ability to represent transformations as a graph.
- question_mark
Evaluates the ability to apply BFS for shortest path or cost calculations.
- question_mark
Assesses how the candidate handles edge cases, such as impossible transformations.
常见陷阱
外企场景- error
Overlooking characters in the source that cannot be transformed to the target.
- error
Incorrectly calculating the cost for a transformation that uses multiple steps.
- error
Not correctly handling the case where no transformation exists between certain characters.
进阶变体
外企场景- arrow_right_alt
Add constraints that limit the number of transformations available.
- arrow_right_alt
Consider dynamic programming approaches for optimizing the cost calculation.
- arrow_right_alt
Introduce the possibility of multiple possible transformations between characters.