# A Python Solution

• After spending quite a while to tune the program, I finally got a Python program to pass all the test cases. I am not sure whether others have better Python solution, but I feel the time restriction is not quite friendly to Python. Let's get to the code.

The idea is essentially BFS, but I've done some preprocessing to make the set of "useful stickers" smaller so that every time I extend my BFS, I can extend fewer states.

``````from collections import Counter
from heapq import heappush, heappop
class Solution(object):
def minStickers(self, stickers, target):
def get_key(cnt):
return "".join(sorted(list(cnt.elements())))

#The first section just make the available number of stickers smaller
#Some stickers will actually have the same results on making the target
#Example (1), if target = 'abc', two stickers 'aef' and 'agh' are actually the same thing
#in terms of making the target, so we only need to reserve one sticker
#Example (2), if target = 'abc', two stickers 'abf' and 'agh'. We only need to reserve `abf`,
#because whatever 'agh' can contribute, we can use 'abf' to achieve the same result,
#or a better one.
target_cnt = Counter(target)
stks_cnt = [Counter(sticker) & target_cnt for sticker in stickers]
stks_key = [get_key(stk) for stk in stks_cnt]
stks_key = sorted(list(set(stks_key)), key = lambda x: -len(x))
stks_cnt = []
for stk_key in stks_key:
sub = False
for cnt in stks_cnt:
if len(Counter(stk_key) - cnt) == 0:
sub = True
if not sub:
stks_cnt.append(Counter(stk_key))
#The result stks_cnt only contains useful stickers that never give the same results
#in the process of making the target. In some cases, only 14 / 50 stickers remained.

visited = set()
target_key = get_key(target_cnt)

#now we have a BFS to search for the minimal number of stickers
queue = [(0, len(target_key), target_key)]
print(len(stks_cnt), len(stickers))

while queue:
#Here, I actuall maintain a priority queue in BFS
#I just want to get the results as early as possible,
#so I prioritize a new state of shorter length
length, key_len, cnt = heappop(queue)
for stk in stks_cnt:
res = Counter(cnt) - stk
key = get_key(res)
if len(key) == 0:
return length + 1
elif key not in visited: