Stickers to Spell Word Python Solution

lcpy gen -n 691   # by problem number
lcpy gen -s stickers_to_spell_word   # by problem name

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3
Explanation: We can use 2 "with" stickers, and 1 "example" sticker.
After cutting and rearrange the letters of those stickers, we can form the target "thehat".
Also, this is the minimum number of stickers necessary to form the target string.

Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1
Explanation: We cannot form the target "basicbasic" from cutting letters from the given stickers.

from functools import cache


class Solution:
    # Time: O(2^m * n * m) where m = len(target), n = len(stickers)
    # Space: O(2^m)
    def min_stickers(self, stickers: list[str], target: str) -> int:
        m = len(target)
        full = (1 << m) - 1
        sticker_counts: list[list[int]] = []
        for sticker in stickers:
            counts = [0] * 26
            for ch in sticker:
                counts[ord(ch) - ord("a")] += 1
            sticker_counts.append(counts)

        @cache
        def dp(mask: int) -> int:
            if mask == full:
                return 0
            # A usable sticker covers at least one letter, so m is an upper bound
            best = m + 1
            for counts in sticker_counts:
                remaining = counts[:]
                new_mask = mask
                for i in range(m):
                    pos = ord(target[i]) - ord("a")
                    if not mask >> i & 1 and remaining[pos]:
                        remaining[pos] -= 1
                        new_mask |= 1 << i
                if new_mask != mask:
                    best = min(best, 1 + dp(new_mask))
            return best

        result = dp(0)
        return result if result <= m else -1