LeetCode 691: Stickers to Spell Word Solution in Python – A Step-by-Step Guide

What Is LeetCode 691: Stickers to Spell Word?

In LeetCode 691: Stickers to Spell Word, you’re given a list of strings stickers, where each string represents characters available on a sticker (e.g., "with" has w, i, t, h), and a string target, the word to spell. Your task is to find the minimum number of stickers needed to form target by selecting characters from the stickers, with each sticker usable any number of times (or not at all). Return this integer, or -1 if impossible. For example, with stickers = ["with", "example", "science"] and target = "thehat", you can use "with" (t, h) and "example" (e, a) to spell "thehat", so return 2. This problem tests your ability to optimize character matching efficiently.

Problem Statement

• Input:
• stickers: List of strings (available stickers).
• target: String (word to spell).
• Output: An integer—minimum stickers needed, or -1 if impossible.
• Rules:
• Each sticker provides its characters (e.g., "with" → w, i, t, h).
• Use each sticker 0 or more times.
• Spell target by selecting characters from stickers.
• Minimize number of stickers used.

Constraints

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

Examples

• Input: stickers = ["with", "example", "science"], target = "thehat"
• Output: 2 ("with" + "example")
• Input: stickers = ["notice", "possible"], target = "basic"
• Output: -1 (No combination works)
• Input: stickers = ["cat", "hat"], target = "cat"
• Output: 1 ("cat")

These examples set the stickers—let’s solve it!

Understanding the Problem: Minimizing Sticker Use

To solve LeetCode 691: Stickers to Spell Word in Python, we need to find the minimum number of stickers from stickers to spell target, using each sticker’s characters any number of times. A brute-force approach—trying all combinations—would be O(n * 2^m * m), where n = len(stickers) and m = len(target), impractical for m ≤ 15 and n ≤ 50. Since we’re matching characters with repetition, dynamic programming with a state representation (e.g., bitmask) or memoized DFS can optimize this by caching subproblem results. We’ll use:

• Best Solution (Dynamic Programming with Bitmask): O(n 2^m m) time, O(2^m) space—fast and optimal.
• Alternative Solution (DFS with Memoization): O(n 2^m m) time, O(n * 2^m) space—intuitive but less space-efficient.

Let’s start with the DP solution, breaking it down for beginners.

Best Solution: Dynamic Programming with Bitmask

Why This Is the Best Solution

The dynamic programming with bitmask approach is the top choice for LeetCode 691 because it’s highly efficient—O(n * 2^m * m) time with O(2^m) space—and uses a bitmask to represent the state of characters spelled in target, dynamically building the minimum stickers needed for each state while leveraging character counts from stickers. It fits constraints (n ≤ 50, m ≤ 15) perfectly and is intuitive once you see the bitmask logic. It’s like flipping bits to spell the word and counting the fewest stickers to get there!

How It Works

Think of this as a bit speller:

• Step 1: Preprocess Stickers:
• Convert each sticker to a character frequency array (e.g., "with" → [0, 0, 0, 1, 0, 0, 0, 1, 1, 0, ..., 1, 0]).
• Step 2: Initialize DP Array:
• dp[mask]: Min stickers to spell characters represented by mask (binary, 1 = spelled).
• dp[0] = 0 (empty string), others infinity.
• Step 3: Fill DP Array:
• For each mask (0 to 2^m - 1):
• For each sticker:
• New mask: Add sticker’s characters, update bits.
• dp[new_mask] = min(dp[new_mask], dp[mask] + 1).
• Step 4: Check Final State:
• Return dp[2^m - 1] if finite, else -1 (all characters spelled).
• Step 5: Return Result:
• Minimum stickers or -1.

It’s like a state builder—mask and minimize!

Step-by-Step Example

Example: stickers = ["ab", "bc"], target = "abc"

• Step 1: Preprocess:
• "ab": [1, 1, 0], "bc": [0, 1, 1].
• target = "abc": [1, 1, 1].
• Step 2: Init:
• m = 3, dp = [0, inf, inf, inf, inf, inf, inf, inf] (2³ states).
• Step 3: Fill DP:
• mask = 0 (000):
• "ab": 001|010 = 011, dp[3] = min(inf, 0+1) = 1.
• "bc": 000|011 = 011, dp[3] = min(1, 0+1) = 1.
• mask = 1 (001):
• "ab": 001|010 = 011, dp[3] = min(1, inf) = 1.
• "bc": 001|011 = 011, dp[3] = min(1, inf) = 1.
• mask = 2 (010):
• "ab": 010|010 = 010, dp[2] = min(inf, inf) = inf.
• "bc": 010|011 = 011, dp[3] = min(1, inf) = 1.
• mask = 3 (011):
• "ab": 011|010 = 011, dp[3] = 1.
• "bc": 011|011 = 011, dp[3] = 1.
• "bc": 011|011 = 111, dp[7] = min(inf, 1+1) = 2.
• Final dp = [0, inf, inf, 1, inf, inf, inf, 2].
• Step 4: dp[7] = 2 (111 = "abc").
• Step 5: Return 2.
• Output: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        # Step 1: Preprocess stickers to char frequency
        m = len(target)
        sticker_freq = []
        for s in stickers:
            freq = [0] * 26
            for char in s:
                freq[ord(char) - ord('a')] += 1
            sticker_freq.append(freq)

        # Step 2: Initialize DP array
        dp = [float('inf')] * (1 << m)
        dp[0] = 0  # Base case: empty string

        # Step 3: Fill DP array
        for mask in range(1 << m):
            if dp[mask] == float('inf'):
                continue
            for freq in sticker_freq:
                new_mask = mask
                target_count = [0] * 26
                # Current target state
                for i in range(m):
                    if mask & (1 << i):
                        target_count[ord(target[i]) - ord('a')] += 1
                # Apply sticker
                for i in range(m):
                    if not (new_mask & (1 << i)) and freq[ord(target[i]) - ord('a')] > target_count[ord(target[i]) - ord('a')]:
                        new_mask |= (1 << i)
                dp[new_mask] = min(dp[new_mask], dp[mask] + 1)

        # Step 4: Check final state
        final_mask = (1 << m) - 1
        return dp[final_mask] if dp[final_mask] != float('inf') else -1

• Lines 4-11: Preprocess: Sticker frequency arrays.
• Lines 14-16: Init: DP array with 2^m states, dp[0] = 0.
• Lines 19-33: Fill:
• For each mask, try each sticker, update new_mask, minimize dp.
• Lines 36-37: Return: dp[full mask] or -1.
• Time Complexity: O(n 2^m m)—n stickers, 2^m states, m chars.
• Space Complexity: O(2^m)—dp array.

This is like a bit crafter—mask and count!

Alternative Solution: DFS with Memoization

Why an Alternative Approach?

The DFS with memoization approach uses recursion—O(n * 2^m * m) time, O(n * 2^m) space. It’s more intuitive, exploring sticker combinations recursively and caching results, but uses more space due to the memo table. It’s like trying stickers one-by-one and remembering what works!

How It Works

Picture this as a sticker explorer:

• Step 1: Preprocess stickers to frequency.
• Step 2: DFS with memo:
• Cache: (target, sticker_idx) → min stickers.
• Base: Empty target = 0.
• Recurse: Try each sticker, reduce target, minimize count.
• Step 3: Return result.

It’s like a memoized speller—try and recall!

Step-by-Step Example

Example: Same as above

• Step 1: Stickers: "ab" [1,1,0], "bc" [0,1,1].
• Step 2: DFS("abc", 0):
• "ab": DFS("c", 0) → "ab": inf, "bc": 1, min=1, total=2.
• "bc": DFS("a", 0) → inf, total=inf.
• Min = 2.
• Step 3: Return 2.
• Output: 2.

Code for DFS Approach

Copy codeclass Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        # Step 1: Preprocess stickers
        sticker_freq = [collections.Counter(s) for s in stickers]

        # Step 2: DFS with memoization
        memo = {}

        def dfs(t: str, idx: int) -> int:
            if not t:
                return 0
            if idx >= len(stickers):
                return float('inf')
            key = (t, idx)
            if key in memo:
                return memo[key]

            # Skip current sticker
            result = dfs(t, idx + 1)
            # Use current sticker
            curr_freq = sticker_freq[idx]
            if any(c in curr_freq for c in t):
                new_target = list(t)
                for c in curr_freq:
                    for _ in range(curr_freq[c]):
                        if c in new_target:
                            new_target.remove(c)
                new_t = ''.join(new_target)
                sub_result = dfs(new_t, idx)
                if sub_result != float('inf'):
                    result = min(result, 1 + sub_result)

            memo[key] = result
            return result

        # Step 3: Start DFS
        ans = dfs(target, 0)
        return ans if ans != float('inf') else -1

• Line 4: Preprocess: Counter for each sticker.
• Lines 7-31: DFS:
• Base: Empty target = 0, out of stickers = inf.
• Skip or use sticker, recurse, cache min.
• Line 34: Return: Start DFS result.
• Time Complexity: O(n 2^m m)—exponential states.
• Space Complexity: O(n * 2^m)—memo table.

It’s a sticker picker—recurse and min!

Comparing the Two Solutions

• DP (Best):
• Pros: O(n 2^m m) time, O(2^m) space, efficient and scalable.
• Cons: Bitmask logic less obvious.
• DFS (Alternative):
• Pros: O(n 2^m m) time, O(n * 2^m) space, intuitive recursion.
• Cons: More space, recursive overhead.

DP wins for space efficiency.

Additional Examples and Edge Cases

• Input: stickers = ["a"], target = "b"
• Output: -1.
• Input: stickers = ["aa"], target = "a"
• Output: 1.

DP handles these well.

Complexity Breakdown

• DP: Time O(n 2^m m), Space O(2^m).
• DFS: Time O(n 2^m m), Space O(n * 2^m).

DP is optimal for space.

Key Takeaways

• DP: Bitmask crafting—smart!
• DFS: Sticker exploring—clear!
• Words: Spelling is fun.
• Python Tip: DP rocks—see Python Basics.

Final Thoughts: Craft That Word

LeetCode 691: Stickers to Spell Word in Python is a fun word challenge. DP with bitmask offers speed and elegance, while DFS with memoization provides a clear alternative. Want more? Try LeetCode 139: Word Break or LeetCode 472: Concatenated Words. Ready to spell? Head to Solve LeetCode 691 on LeetCode and stick those letters together today!