#
# @lc app=leetcode id=691 lang=python3
#
# [691] Stickers to Spell Word
#

# @lc code=start
from collections import deque


class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        # queue stores a collection of (target, count) tuples.
        # target: the remaining substring to be spelled.
        # count: the number stickers used so far
        queue = deque([(target, 0)])

        while queue:
            cur_target, count = queue.popleft()
            for sticker in stickers:
                next_target = cur_target
                if next_target[0] not in sticker:
                    continue
                for ch_s in sticker:
                    for idx, ch in enumerate(next_target):
                        # If we find a char matching from the sticker,
                        # update the target and move on to next char of the
                        # sticker.
                        # We need to make sure each char in sticker can be
                        # used at most one time.
                        if ch == ch_s:
                            next_target = next_target[:idx] + next_target[idx +
                                                                          1:]
                            break
                if next_target == "":
                    return count + 1
                queue.append((next_target, count + 1))
        return -1


class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n = len(target)
        N = (1 << n)
        # Use n bits to store the status.
        # For example, if n is 5, and target is "hello",
        # 00110 means that "ll" is spelled.
        # 00110 => 6 as an integer value.
        # We can do a bottom up dp trying to get 00000 => 11111 (final status)
        dp = [float('inf')] * N
        dp[0] = 0

        # Building the dp in a bottom up manner
        for i in range(N):
            if dp[i] == float('inf'):
                continue
            for sticker in stickers:
                j = self.findNextStatus(i, target, sticker)
                if j == i: continue
                dp[j] = min(dp[j], dp[i] + 1)
        return -1 if dp[-1] == float('inf') else dp[-1]

    def findNextStatus(self, status, target, sticker):
        for ch in sticker:
            for i in range(len(target)):

                # Check if the i-th char in target is spelled or not
                # and if current ch matches the i-th char in target
                if ((status >> i) & 1) == 0 and target[i] == ch:

                    # Found one valid char, use it and update the status
                    status += (1 << i)

                    # Break out of the inner loop so that current "ch" will
                    # only be used once from the sticker.
                    break
        return status


# @lc code=end
