Stickers to Spell Word — LeetCode 691 Python Solution
HardBit ManipulationMemoizationArrayHash TableStringDynamic ProgrammingBacktrackingBitmask
- Problem
- #691
- Pattern
- Backtracking
- Reading time
- 4 min
- Source
- leetcode.com
The problem
We are given n different types of stickers. Each sticker has a lowercase English word on it.
Example
- Input
- stickers = ["with","example","science"], target = "thehat"
- Output
- 3
- Explanation
- We can use 2 "with" stickers, and 1 "example" sticker.
Python solution
Python
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 -1Complexity
| Measure | Complexity |
|---|---|
| Time | O(2^n \times m \times (l + n)) |
| Space | O(2^n) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 691. Stickers to Spell Word is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 691. Stickers to Spell Word?
- LeetCode 691. Stickers to Spell Word is rated Hard on LeetCode.
- What is the time complexity of LeetCode 691. Stickers to Spell Word?
- The Python solution on this page runs in O(2^n \times m \times (l + n)).
- What is the space complexity of LeetCode 691. Stickers to Spell Word?
- The Python solution on this page uses O(2^n) auxiliary space.
- What topics does LeetCode 691. Stickers to Spell Word cover?
- LeetCode 691. Stickers to Spell Word is tagged Bit Manipulation, Memoization, Array, Hash Table, String, Dynamic Programming, Backtracking and Bitmask on LeetCode.