LeetCode 题解工作台
转换字符串的最小成本 II
给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。 另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串…
6
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
根据题目描述，我们可以将每个字符串看作一个节点，每对字符串的转换成本看作一条有向边。那么我们先初始化一个 $26 \times 26$ 的二维数组 ，其中 表示字符串 转换成字符串 的最小成本。初始时 $g[i][j] = \infty$，如果 $i = j$，那么 $g[i][j] = 0$。在这里，我们可以借助字典树存储 `original` 和 `changed` 中的字符串以及对应的…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个下标从 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[a..b]和source[c..d]，满足b < c或d < a。换句话说，两次操作中选择的下标 不相交 。 - 在两次操作中选择的子串分别是
source[a..b]和source[c..d]，满足a == c且b == d。换句话说，两次操作中选择的下标 相同 。
返回将字符串 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"，执行以下操作： - 将子串 source[1..1] 从 "b" 改为 "c" ，成本为 5 。 - 将子串 source[2..2] 从 "c" 改为 "e" ，成本为 1 。 - 将子串 source[2..2] 从 "e" 改为 "b" ，成本为 2 。 - 将子串 source[3..3] 从 "d" 改为 "e" ，成本为 20 。 产生的总成本是 5 + 1 + 2 + 20 = 28 。 可以证明这是可能的最小成本。
示例 2：
输入：source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5] 输出：9 解释：将 "abcdefgh" 转换为 "acdeeghh"，执行以下操作： - 将子串 source[1..3] 从 "bcd" 改为 "cde" ，成本为 1 。 - 将子串 source[5..7] 从 "fgh" 改为 "thh" ，成本为 3 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交。 - 将子串 source[5..7] 从 "thh" 改为 "ghh" ，成本为 5 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交，且与第二次操作选中的下标相同。 产生的总成本是 1 + 3 + 5 = 9 。 可以证明这是可能的最小成本。
示例 3：
输入：source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578] 输出：-1 解释：无法将 "abcdefgh" 转换为 "addddddd" 。 如果选择子串 source[1..3] 执行第一次操作，以将 "abcdefgh" 改为 "adddefgh" ，你无法选择子串 source[3..7] 执行第二次操作，因为两次操作有一个共用下标 3 。 如果选择子串 source[3..7] 执行第一次操作，以将 "abcdefgh" 改为 "abcddddd" ，你无法选择子串 source[1..3] 执行第二次操作，因为两次操作有一个共用下标 3 。
提示：
1 <= source.length == target.length <= 1000source、target均由小写英文字母组成1 <= cost.length == original.length == changed.length <= 1001 <= original[i].length == changed[i].length <= source.lengthoriginal[i]、changed[i]均由小写英文字母组成original[i] != changed[i]1 <= cost[i] <= 106
解题思路
方法一：字典树 + Floyd 算法 + 记忆化搜索
根据题目描述，我们可以将每个字符串看作一个节点，每对字符串的转换成本看作一条有向边。那么我们先初始化一个 的二维数组 ，其中 表示字符串 转换成字符串 的最小成本。初始时 ，如果 ，那么 。在这里，我们可以借助字典树存储 original 和 changed 中的字符串以及对应的整数编号。
然后，我们使用 Floyd 算法计算出任意两个字符串之间的最小成本。
接下来，我们定义函数 表示将字符串 转换为字符串 所需的最小成本。那么答案就是 。
函数 的计算过程如下：
- 如果 ，说明不需要转换，返回 。
- 否则，如果 ，那么可以直接跳过，我们直接递归计算 。我们也可以在 的范围内枚举下标 ，如果 和 都在字典树中，且其对应的整数编号 和 都大于等于 ，那么我们可以将 和 相加，得到一种转换方案的成本，我们取所有方案中的最小值。
综上，我们可以得到：
其中 和 分别是 和 在字典树中对应的整数编号。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度。
class Node:
__slots__ = ["children", "v"]
def __init__(self):
self.children: List[Node | None] = [None] * 26
self.v = -1
class Solution:
def minimumCost(
self,
source: str,
target: str,
original: List[str],
changed: List[str],
cost: List[int],
) -> int:
m = len(cost)
g = [[inf] * (m << 1) for _ in range(m << 1)]
for i in range(m << 1):
g[i][i] = 0
root = Node()
idx = 0
def insert(w: str) -> int:
node = root
for c in w:
i = ord(c) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
if node.v < 0:
nonlocal idx
node.v = idx
idx += 1
return node.v
@cache
def dfs(i: int) -> int:
if i >= len(source):
return 0
res = dfs(i + 1) if source[i] == target[i] else inf
p = q = root
for j in range(i, len(source)):
p = p.children[ord(source[j]) - ord("a")]
q = q.children[ord(target[j]) - ord("a")]
if p is None or q is None:
break
if p.v < 0 or q.v < 0:
continue
res = min(res, dfs(j + 1) + g[p.v][q.v])
return res
for x, y, z in zip(original, changed, cost):
x = insert(x)
y = insert(y)
g[x][y] = min(g[x][y], z)
for k in range(idx):
for i in range(idx):
if g[i][k] >= inf:
continue
for j in range(idx):
# g[i][j] = min(g[i][j], g[i][k] + g[k][j])
if g[i][k] + g[k][j] < g[i][j]:
g[i][j] = g[i][k] + g[k][j]
ans = dfs(0)
return -1 if ans >= inf else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the number of substring operations and the length of source. Mapping strings to IDs and iterating over operations leads to O(n * m) worst-case, with n = source length and m = number of operations. Space is dominated by dp array and substring mapping. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate correctly handles non-overlapping or identical index rules.
- question_mark
Observe if state transition DP is applied efficiently with substring mapping.
- question_mark
Listen for reasoning about impossible conversions and early pruning strategies.
常见陷阱
外企场景- error
Forgetting to enforce non-overlapping or identical index constraint between operations.
- error
Failing to efficiently match substrings, leading to TLE on larger inputs.
- error
Ignoring edge cases where conversion is impossible, returning wrong positive cost.
进阶变体
外企场景- arrow_right_alt
Allow wildcard characters in original substrings to match multiple target sequences.
- arrow_right_alt
Minimize number of operations instead of total cost while using the same DP framework.
- arrow_right_alt
Restrict operations to contiguous blocks of fixed maximum length to test optimized DP transitions.