原文链接: https://leetcode-cn.com/problems/stickers-to-spell-word

英文原文

We are given n different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given string target by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.

Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.

 

Example 1:

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation:
We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.

Example 2:

Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
Explanation:
We cannot form the target "basicbasic" from cutting letters from the given stickers.

 

Constraints:

• n == stickers.length
• 1 <= n <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target <= 15
• stickers[i] and target consist of lowercase English letters.

中文题目

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。

你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。

如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。

拼出目标 target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。

 

示例 1：

输入：

["with", "example", "science"], "thehat"

输出：

3

解释：

我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2：

输入：

["notice", "possible"], "basicbasic"

输出：

-1

解释：

我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

 

提示：

• stickers 长度范围是 [1, 50]。
• stickers 由小写英文单词组成（不带撇号）。
• target 的长度在 [1, 15] 范围内，由小写字母组成。
• 在所有的测试案例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选取的，目标是两个随机单词的串联。
• 时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。

 

通过代码

官方题解

方法一：优化穷举搜索

答案是彻底搜索贴纸的组合。因为数据是随机化的，所以有很多启发式方法可以帮助我们更快地实现这一目标。

• 对于所有的贴纸，我们可以忽略目标单词中没有的任何字母。
• 当我们的候选答案不会小于我们已经找到的答案时，我们可以停止搜索此路径。
• 我们应该尽量让我们的详尽搜索尽快绑定到答案，因此上面描述的效果会更频繁的发生。
• 当一个贴纸占主导地位时，我们不应该将被主导地位的贴纸纳入我们的贴纸收藏中。[这里我们说，如果 A.count(letter) >= B.count(letter) ,letter 代表所有字母，则贴纸 A 占 B 的主导地位。]

算法：

• 首先，对于每个贴纸，让我们创建一个哈希表存储贴纸中的含有目标单词中的字母计数（mapping letter -> sticker.count(letter)）。A 是记录贴纸中含有目标单词字母数量的数组。另外，让我们创建 t_count，记录目标单词的字母数量。
• 其次，让我们去掉被主导的贴纸。我们只需要检查一次贴纸是否由其他贴纸主导，那些不被主导的贴纸包含在我们的收藏中。
• 我们现在准备开始彻底搜查。调用 search(ans) 表示我们要确定可以在 A 中使用的最小贴纸数，以满足目标计数 t_count。ans 将存储当前形成的答案，best 将存储当前最佳答案。
• 如果我们当前的答案不能超过当前的最佳答案，我们应该停止搜索。若我们的目标是满意的，我们应该更新我们的答案。
• 否则，我们想知道我们可以使用的这个贴纸的最大数量。例如，如果这个标签是 'abb'，我们的目标是 'aaabbbbccccc'，那么我们最多可以使用 3 个贴纸。这是 math.ceil(target.count(letter) / sticker.count(letter)) 的最大值，它接管了 sticker 中的所有字母。我们称之为 used。
• 之后，对于我们目前正在考虑的贴纸，我们尝试 used 它们，然后 used - 1，used - 2 等等。我们这样做的原因是为了更快地获得最佳值，这将阻止我们穷尽搜索的其他分支继续进行。

复杂度分析

• 时间复杂度：$N$ 作为贴纸的数目，$T$ 作为目标单词的字母数目。时间复杂度的界限是 $O(N^{T+1} T^2)$：对于每个贴纸，我们必须尝试使用它最多 $T+1$ 次，并更新我们的目标计数成本 $O(T)$，我们最多做 $T$ 次。或者，由于答案的范围是 $T$ 的，我们可以证明我们最多只能搜索 $\binom{N+T-1}{T-1}$ 次。这将是 $O(\binom{N+T-1}{T-1} T^2)$。
• 空间复杂度：$O(N+T)$，在调用 search 时存储 stickersCount、targetcount 并处理递归调用堆栈。

方法二：动态规划

对于每一个状态，我们现在就来处理它，看看在应用一个贴纸之后会发生什么。对于贴纸中可以满足字母的状态的位，我们设置 state（now |= 1 << i）。最后，我们知道现在是将该贴纸应用到贴纸的结果，并且我们适当地更新了我们的 dp。

复杂度分析

• 时间复杂度：$O(2^T * S * T)$ 其中 $S$ 是所有贴纸中的字母总数，$T$ 是目标单词中的字母数。我们可以仔细检查每个循环，得出这个结论。
• 空间复杂度：$O(2^T)$，dp 使用的空间。

统计信息

通过次数	提交次数	AC比率
3908	7979	49.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
赎金信	简单