LeetCode Solutions Blog

Stickers to Spell Word

Number: 691

Difficulty: Hard

Paid? No

Problem Description

Given a list of stickers, where each sticker is represented by a lowercase English word, and a target string, determine the minimum number of stickers needed to form the target. You can use each sticker as many times as needed, and you can cut individual letters from the stickers to rearrange them to form the target. Return -1 if it is impossible to form the target using the given stickers.

Key Insights

Precompute frequency counts for letters in each sticker to make lookup efficient.
Use recursion (depth-first search) to try different sticker combinations for reducing the target.
Implement memoization to cache and recall the results for intermediate target strings, reducing redundant computations.
Use a greedy filter: if a sticker does not contain the first letter of the current target, skip it to optimize performance.
The problem is reduced to finding the minimum number of stickers that can reduce the target string to an empty string.

Space and Time Complexity

Time Complexity: Exponential in the worst-case scenario. The use of memoization significantly reduces redundant computations, though worst-case remains O(2^T * S) where T is the length of target and S is the number of stickers. Space Complexity: O(2^T) for memoization in the worst-case, plus O(T) recursion depth.

Solution

The solution employs recursion with memoization. First, count the frequency of each letter in every sticker. Then, define a recursive helper that reduces the target by selecting a sticker that contributes at least one letter from the target. To ensure consistency and avoid duplicate states, the remaining target string is sorted. If no sticker can reduce the target further, return -1. Cache computed results in a memoization hash map to avoid re-computation for the same target string state. This approach efficiently explores combinations and returns the minimal number of stickers required.

Code Solutions

def minStickers(stickers, target):
    # Precompute letter frequencies for each sticker.
    n = len(stickers)
    sticker_counts = []
    for word in stickers:
        count = [0] * 26
        for ch in word:
            count[ord(ch) - ord('a')] += 1
        sticker_counts.append(count)
    
    # Memoization dictionary: key is sorted remaining target, value is minimum stickers needed.
    memo = {"": 0}
    
    def helper(rem_target):
        if rem_target in memo:
            return memo[rem_target]
        
        # Count frequency for each letter in the remaining target.
        target_count = [0] * 26
        for ch in rem_target:
            target_count[ord(ch) - ord('a')] += 1
        
        min_stickers = float('inf')
        # Try every sticker to reduce the target.
        for sticker in sticker_counts:
            # Optimization: skip the sticker if it doesn't contain the first letter of rem_target.
            if sticker[ord(rem_target[0]) - ord('a')] == 0:
                continue
            # Build the new target as a string after using the current sticker.
            new_target = []
            for i in range(26):
                if target_count[i] > 0:
                    # Calculate remaining count for character after applying sticker.
                    remain = max(0, target_count[i] - sticker[i])
                    new_target.extend([chr(i + ord('a'))] * remain)
            # Sort new target for consistency in memo.
            new_target_str = "".join(sorted(new_target))
            result = helper(new_target_str)
            if result != -1:
                min_stickers = min(min_stickers, 1 + result)
            # Continue trying other stickers.
        memo[rem_target] = -1 if min_stickers == float('inf') else min_stickers
        return memo[rem_target]
    
    # Sort target for consistency.
    return helper("".join(sorted(target)))


# Example usage:
stickers = ["with", "example", "science"]
target = "thehat"
print(minStickers(stickers, target))  # Output: 3