⚡Flashcard Drill➔
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

  1. The state is the multiset of target letters still needed; represent it as the remaining string and memoise on it.
  2. From a state, applying a sticker removes as many of each needed letter as the sticker supplies.
  3. Force every sticker to cover the first remaining letter, which prunes symmetric orderings of the same sticker set.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems