What is the main pattern used in Stickers to Spell Word?

The core pattern is array scanning plus hash lookup, using frequency maps of stickers to track letters and recursively cover the target.

Can each sticker be used multiple times?

Yes, each sticker can be reused infinitely, but you must account for its letter counts when forming the target.

Why is memoization important for this problem?

Memoization avoids recalculating the minimum stickers for the same remaining target, drastically reducing recursive calls and runtime.

What should I do if a target cannot be formed?

Return -1 immediately if no sticker combination can cover all letters of the target, as indicated by the recursive exploration.

How does pruning irrelevant stickers improve performance?

Skipping stickers that add no new letters prevents unnecessary recursive branches, reducing the combinatorial explosion inherent in exhaustive search.

#691

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。注意：…

数组哈希表字符串动态规划回溯

题目描述

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：

输入： stickers = ["with","example","science"], target = "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入：stickers = ["notice","possible"], target = "basicbasic"
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:

n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] 和 target 由小写英文单词组成

lightbulb

解题思路

方法一：BFS + 状态压缩

我们注意到，字符串 $\textit{target}$ 的长度不超过 $15$ ，我们可以使用一个长度为 $15$ 的二进制数来表示 $\textit{target}$ 的每个字符是否被拼出，如果第 $i$ 位为 $1$ ，表示 $\textit{target}$ 的第 $i$ 个字符已经被拼出，否则表示未被拼出。

我们定义一个初始状态 $0$ ，表示所有字符都未被拼出，然后我们使用广度优先搜索的方法，从初始状态开始，每次搜索时，我们枚举所有的贴纸，对于每一张贴纸，我们尝试拼出 $\textit{target}$ 的每一个字符，如果拼出了某个字符，我们就将对应的二进制数的第 $i$ 位设置为 $1$ ，表示该字符已经被拼出，然后我们继续搜索，直到我们拼出了 $\textit{target}$ 的所有字符。

时间复杂度 $O(2^n \times m \times (l + n))$ ，空间复杂度 $O(2^n)$ 。其中 $n$ 是字符串 $\textit{target}$ 的长度，而 $m$ 和 $l$ 分别是贴纸的数量和贴纸的平均长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(target)
        q = deque([0])
        vis = [False] * (1 << n)
        vis[0] = True
        ans = 0
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == (1 << n) - 1:
                    return ans
                for s in stickers:
                    cnt = Counter(s)
                    nxt = cur
                    for i, c in enumerate(target):
                        if (cur >> i & 1) == 0 and cnt[c] > 0:
                            cnt[c] -= 1
                            nxt |= 1 << i
                    if not vis[nxt]:
                        vis[nxt] = True
                        q.append(nxt)
            ans += 1
        return -1

speed

复杂度分析

指标	值
时间	complexity is O(2^T * S * T), where T is the target length and S is the number of stickers, due to the recursive exploration of all target subsets with each sticker. Space complexity is O(2^T) for memoization storing subsets of the target.
空间	O(2^T)

psychology

面试官常问的追问

外企场景

question_mark
Look for solutions using array scanning combined with hash maps to track letter frequencies.
question_mark
Expect candidates to discuss memoization to avoid repeated calculations in the combinatorial search.
question_mark
Watch for pruning strategies that reduce unnecessary recursive calls when stickers contribute no new letters.

warning

常见陷阱

外企场景

error
Failing to memoize results, causing exponential time due to redundant recursive calls.
error
Attempting to use each sticker only once rather than allowing multiple uses.
error
Not pruning stickers that do not contribute to the remaining target, leading to wasted computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Limiting the number of times each sticker can be used, requiring more careful counting.
arrow_right_alt
Target words with repeated letters appearing more than any single sticker can provide, testing aggregation logic.
arrow_right_alt
Stickers with overlapping letters where multiple sticker combinations yield the same target letters, challenging pruning strategies.

help

常见问题

外企场景

继续练习

#698 划分为k个相等的子集 #638 大礼包 #996 平方数组的数目