LeetCode 题解工作台
最小代价构造字符串
给你一个字符串 target 、一个字符串数组 words 以及一个整数数组 costs ，这两个数组长度相同。 设想一个空字符串 s 。 你可以执行以下操作任意次数（包括 零 次）： 选择一个在范围 [0, words.length - 1] 的索引 i 。 将 words[i] 追加到 s 。 …
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示构造 前 个字符的最小代价，初始时 $f[0] = 0$，其余值均为无穷大。答案为 ，其中 是 的长度。 对于当前 ，考虑枚举单词的长度 ，如果 $j \leq i$，那么我们可以考虑从 $i - j + 1$ 到 这段区间的哈希值，如果这个哈希值对应的单词存在，那么我们可以转移从 $f[i - j]$ 转移到 。状态转移方程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。
设想一个空字符串 s。
你可以执行以下操作任意次数（包括 零 次）：
- 选择一个在范围
[0, words.length - 1]的索引i。 - 将
words[i]追加到s。 - 该操作的成本是
costs[i]。
返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。
示例 1：
输入： target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]
输出： 7
解释：
- 选择索引 1 并以成本 1 将
"abc"追加到s，得到s = "abc"。 - 选择索引 2 并以成本 1 将
"d"追加到s，得到s = "abcd"。 - 选择索引 4 并以成本 5 将
"ef"追加到s，得到s = "abcdef"。
示例 2：
输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]
输出： -1
解释：
无法使 s 等于 target，因此返回 -1。
提示：
1 <= target.length <= 5 * 1041 <= words.length == costs.length <= 5 * 1041 <= words[i].length <= target.length- 所有
words[i].length的总和小于或等于5 * 104 target和words[i]仅由小写英文字母组成。1 <= costs[i] <= 104
解题思路
方法一：字符串哈希 + 动态规划 + 枚举长度
我们定义 表示构造 前 个字符的最小代价，初始时 ，其余值均为无穷大。答案为 ，其中 是 的长度。
对于当前 ，考虑枚举单词的长度 ，如果 ，那么我们可以考虑从 到 这段区间的哈希值，如果这个哈希值对应的单词存在，那么我们可以转移从 转移到 。状态转移方程如下：
其中 表示长度为 的单词且哈希值与 相同的单词的最小代价。
时间复杂度 ，空间复杂度 。其中 是 的长度，而 是数组 中所有单词的长度之和。
class Solution:
def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
base, mod = 13331, 998244353
n = len(target)
h = [0] * (n + 1)
p = [1] * (n + 1)
for i, c in enumerate(target, 1):
h[i] = (h[i - 1] * base + ord(c)) % mod
p[i] = (p[i - 1] * base) % mod
f = [0] + [inf] * n
ss = sorted(set(map(len, words)))
d = defaultdict(lambda: inf)
min = lambda a, b: a if a < b else b
for w, c in zip(words, costs):
x = 0
for ch in w:
x = (x * base + ord(ch)) % mod
d[x] = min(d[x], c)
for i in range(1, n + 1):
for j in ss:
if j > i:
break
x = (h[i] - h[i - j] * p[j]) % mod
f[i] = min(f[i], f[i - j] + d[x])
return f[n] if f[n] < inf else -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N * M) in the worst case where N is target length and M is total sum of words length, optimized by efficient word matching. Space complexity is O(N) for the DP array plus additional structures for string matching. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check for overlapping word matches that could reduce total cost.
- question_mark
Notice when certain prefixes cannot be completed, signaling a -1 result.
- question_mark
Expect usage of hashing or trie-based structures to manage many word transitions.
常见陷阱
外企场景- error
Failing to reuse words correctly leading to higher cost than necessary.
- error
Ignoring the order of words causing invalid string construction.
- error
Inefficient substring matching causing TLE on large input sizes.
进阶变体
外企场景- arrow_right_alt
Change costs array to allow negative values and require handling minimal net cost.
- arrow_right_alt
Restrict each word to be used at most once and compute the minimal cost.
- arrow_right_alt
Find all possible minimal cost sequences instead of just the total minimal cost.