Stickers to Spell Word Solution in Python

Problem Description

Ah, the classic “Stickers to Spell Word” problem! Imagine you’re at a birthday party, and you want to spell out “Happy Birthday” using those colorful stickers you found in the party supply box. But wait! You only have a limited number of stickers, and they don’t even have all the letters you need. Sounds like a fun challenge, right?

In this LeetCode problem, you are given a list of stickers, each containing a collection of letters, and a target word that you want to spell out. Your mission, should you choose to accept it, is to determine the minimum number of stickers required to spell the target word. If it’s impossible, you’ll return -1.

Code Solution


class Solution:
    def minStickers(self, stickers: list[str], target: str) -> int:
        maxMask = 1 << len(target)
        dp = [math.inf] * maxMask
        dp[0] = 0

        for mask in range(maxMask):
            if dp[mask] == math.inf:
                continue
            for sticker in stickers:
                superMask = mask
                for c in sticker:
                    for i, t in enumerate(target):
                        if c == t and not (superMask >> i & 1):
                            superMask |= 1 << i
                            break
                dp[superMask] = min(dp[superMask], dp[mask] + 1)

        return -1 if dp[-1] == math.inf else dp[-1]

Approach Explanation

The approach taken in this solution is a classic dynamic programming technique combined with bit manipulation. Here’s a brief breakdown:

Bitmask Representation: Each state of the target word is represented as a bitmask, where each bit indicates whether a letter in the target has been covered or not.
Dynamic Programming Array: An array dp is used to store the minimum number of stickers needed to achieve each state (bitmask) of the target word.
Iterate Through Masks: For each possible state (mask), the algorithm checks if it can be expanded by using each sticker. If a sticker can cover a letter that is still missing in the current state, the new state (superMask) is calculated.
Update DP Array: The dp array is updated with the minimum number of stickers needed to reach the new state.
Final Result: The result is found in dp[-1], which represents the state where all letters of the target are covered.

Time and Space Complexity

Time Complexity: O(n * m * 2^k), where n is the number of stickers, m is the average length of the stickers, and k is the length of the target word.

Space Complexity: O(2^k), which is the size of the dp array that stores the minimum stickers needed for each state.

Real-World Example

Imagine you’re trying to create a custom birthday card for your best friend. You have a bunch of stickers with letters, but they don’t quite cover the phrase "Happy Birthday." You might have to use multiple stickers to get all the letters you need. This problem is just like that! You need to figure out the least number of stickers to use to get the perfect message across.