Leetcode 691 Solution

class Solution:
    def minStickers(self, stickers, target):
        if not target:
            return 0

        def get_cnt(s):
            cnt = [0] * 26
            for ch in s:
                cnt[ord(ch) - ord('a')] += 1
            return cnt

        target_cnt = get_cnt(target)
        sticker_cnts = [get_cnt(sticker) for sticker in stickers]

        q = collections.deque()
        q.append(target_cnt)
        visited = set()

        step = 0
        while q:
            s = len(q)

            step += 1
            for _ in range(s):
                node_cnt = q.popleft()
                visited.add(",".join([str(cnt) for cnt in node_cnt]))

                first_ch_index = 0
                for i in range(26):
                    if node_cnt[i] > 0:
                        first_ch_index = i
                        break

                for sticker_cnt in sticker_cnts:
                    if sticker_cnt[first_ch_index] == 0:
                        continue

                    child_node_cnt = list(node_cnt)

                    for i in range(26):
                        child_node_cnt[i] = max(0, child_node_cnt[i] - sticker_cnt[i])

                    if sum(child_node_cnt) == 0:
                        return step

                    if ",".join([str(cnt) for cnt in child_node_cnt]) not in visited:
                        q.append(child_node_cnt)

        return -1