LeetCode 题解工作台
形成目标字符串需要的最少字符串数 II
给你一个字符串数组 words 和一个字符串 target 。 如果字符串 x 是 words 中 任意 字符串的 前缀 ，则认为 x 是一个 有效 字符串。 现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target ，则返…
8
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
由于本题数据规模较大，使用“字典树 + 记忆化搜索”的方法将会超时，我们需要寻找一种更高效的解法。 考虑从字符串 的第 个字符开始，最远能够匹配的字符串长度，假设为 ，那么对于任意 $j \in [i, i + \textit{dist}-1]$，我们都能够在 中找到一个字符串，使得 是这个字符串的前缀。这存在着单调性，我们可以使用二分查找来确定 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串数组 words 和一个字符串 target。
如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
示例 1：
输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
输出： 3
解释：
target 字符串可以通过连接以下有效字符串形成：
words[1]的长度为 2 的前缀，即"aa"。words[2]的长度为 3 的前缀，即"bcd"。words[0]的长度为 3 的前缀，即"abc"。
示例 2：
输入： words = ["abababab","ab"], target = "ababaababa"
输出： 2
解释：
target 字符串可以通过连接以下有效字符串形成：
words[0]的长度为 5 的前缀，即"ababa"。words[0]的长度为 5 的前缀，即"ababa"。
示例 3：
输入： words = ["abcdef"], target = "xyz"
输出： -1
提示：
1 <= words.length <= 1001 <= words[i].length <= 5 * 104- 输入确保
sum(words[i].length) <= 105. words[i]只包含小写英文字母。1 <= target.length <= 5 * 104target只包含小写英文字母。
解题思路
方法一：字符串哈希 + 二分查找 + 贪心
由于本题数据规模较大，使用“字典树 + 记忆化搜索”的方法将会超时，我们需要寻找一种更高效的解法。
考虑从字符串 的第 个字符开始，最远能够匹配的字符串长度，假设为 ，那么对于任意 ，我们都能够在 中找到一个字符串，使得 是这个字符串的前缀。这存在着单调性，我们可以使用二分查找来确定 。
具体地，我们首先预处理出 中所有字符串的每个前缀的哈希值，按照前缀长度分组存储在 数组中。另外，将 的哈希值也预处理出来，存储在 中，便于我们查询任意 的哈希值。
接下来，我们设计一个函数 ，表示从字符串 的第 个字符开始，最远能够匹配的字符串长度。我们可以通过二分查找的方式确定 。
定义二分查找的左边界 ，右边界 ，其中 是字符串 的长度，而 是 中字符串的最大长度。在二分查找的过程中，我们需要判断 是否是 中的某个哈希值，如果是，则将左边界 更新为 ，否则将右边界 更新为 。二分结束后，返回 即可。
算出 后，问题就转化为了一个经典的贪心问题，我们从 开始，对于每个位置 ，最远可以移动到的位置为 ，求最少需要多少次移动即可到达终点。
我们定义 表示上一次移动的位置，变量 表示当前位置能够移动到的最远位置，初始时 。我们从 开始遍历，如果 等于 ，说明我们需要再次移动，此时如果 ，说明我们无法再移动，返回 ；否则，我们将 更新为 ，并将答案加一。
遍历结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 是字符串 的长度，而 是所有有效字符串的总长度。
class Hashing:
__slots__ = ["mod", "h", "p"]
def __init__(self, s: List[str], base: int, mod: int):
self.mod = mod
self.h = [0] * (len(s) + 1)
self.p = [1] * (len(s) + 1)
for i in range(1, len(s) + 1):
self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
self.p[i] = (self.p[i - 1] * base) % mod
def query(self, l: int, r: int) -> int:
return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod
class Solution:
def minValidStrings(self, words: List[str], target: str) -> int:
def f(i: int) -> int:
l, r = 0, min(n - i, m)
while l < r:
mid = (l + r + 1) >> 1
sub = hashing.query(i + 1, i + mid)
if sub in s[mid]:
l = mid
else:
r = mid - 1
return l
base, mod = 13331, 998244353
hashing = Hashing(target, base, mod)
m = max(len(w) for w in words)
s = [set() for _ in range(m + 1)]
for w in words:
h = 0
for j, c in enumerate(w, 1):
h = (h * base + ord(c)) % mod
s[j].add(h)
ans = last = mx = 0
n = len(target)
for i in range(n):
dist = f(i)
mx = max(mx, i + dist)
if i == last:
if i == mx:
return -1
last = mx
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N * L * W) where N is target length, L is maximum word length, and W is number of words, optimized with prefix hashing. Space complexity is O(N + total prefix storage) for DP and prefix structures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Mentions state transition dynamic programming and prefix concatenation strategy.
- question_mark
Asks about optimizing substring checks and reducing DP iteration overhead.
- question_mark
Explores edge cases where target cannot be formed or words are very long.
常见陷阱
外企场景- error
Failing to consider all valid prefixes leads to incorrect DP updates.
- error
Using naive substring comparisons results in TLE for large input sizes.
- error
Returning wrong index offset or missing initial DP initialization at zero.
进阶变体
外企场景- arrow_right_alt
Limit reuse of words to at most once per concatenation, changing DP transitions.
- arrow_right_alt
Count all distinct ways to form target instead of minimum number.
- arrow_right_alt
Extend to allow words containing wildcards that match multiple characters.