NeetCode #685LC-691Hard1-D Dynamic Programming
← Back to All Problems#685 · #691 · Stickers to Spell Word(贴纸拼词)
📌 Problem Statement & Constraints
Given an array of
stickers (each a string of lowercase letters) and a target string, return the minimum number of stickers needed to spell the target, or -1 if it is impossible. Each sticker may be used multiple times, and each use consumes its letters. Constraints: 1 <= stickers.length <= 50, 1 <= stickers[i].length <= 10, 1 <= target.length <= 15.💡 Core Algorithmic Approaches
- The state is the multiset of target letters still needed; represent it as the remaining string and memoise on it.
- From a state, applying a sticker removes as many of each needed letter as the sticker supplies.
- Force every sticker to cover the first remaining letter, which prunes symmetric orderings of the same sticker set.
- Return the minimum over all stickers, or infinity when no sticker can cover the first letter.
💻 Benchmark Python3 Implementation
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
from collections import Counter
from functools import lru_cache
stick = [] # letter counts of stickers, deduplicated
for s in stickers:
cnt = Counter(c for c in s if c in target)
if cnt and cnt not in stick:
stick.append(cnt)
@lru_cache(maxsize=None)
def dfs(remain: str) -> int:
if not remain:
return 0
best = float("inf")
need = Counter(remain)
for cnt in stick:
if remain[0] not in cnt:
continue # this sticker cannot cover the first letter
nxt = []
for ch, k in need.items():
left = k - cnt.get(ch, 0)
if left > 0:
nxt.append(ch * left)
best = min(best, 1 + dfs("".join(nxt)))
return best
ans = dfs(target)
return ans if ans != float("inf") else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
Exponential in the number of distinct states, but bounded by the target length (n <= 15); memoisation keeps it practical.
💾 Space Complexity
O(number of reachable states) for the memo table.
⚠️ Interview Pitfalls & Follow-ups
- Not forcing the first remaining letter to be covered: requiring each sticker to cover
remain[0]removes symmetric states and speeds up the search. - Memoising on something other than the remaining multiset: the state must capture exactly which letters are left, or results will be wrong.
- Assuming a sticker can be used partially: each use consumes all the letters it supplies at once.
- Omitting the -1 case: when no combination of stickers covers the target, the answer is -1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.