A Python Solution

  • 1

    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:
            #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:
                        heappush(queue, (length + 1, len(key), key))
            return -1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.