Python BFS


  • 0

    Tried hashing tuples of remaining characters in sorted order but the code timed out. After thinking about it a bit, switched the logic to hash alphabet arrays (26 size for each letter of the lowercase alphabet), which made it a lot faster. I thought creating a list of tuples of (key, value) pairs for remaining characters would be faster since it'll take less to copy the hashmap in each iteration and sorting a list of tuples with unique alphabets wouldn't be a major performance choke point since the longest variation of the list would be 26.

            def minStickers(self, stickers, target):
            """
            :type stickers: List[str]
            :type target: str
            :rtype: int
            """
            unique, visited, arr = set(), set(), [0] * 26
            required, base = len(target), ord('a')
            chars = collections.Counter(target)
            for c in chars:
                arr[ord(c)-base] = chars[c]
            for s in stickers:
                c = collections.Counter(s)
                temp = [(ord(key)-base, c[key]) for key in c if key in chars]
                if temp: unique.add(tuple(temp))
            queue = collections.deque([(arr, required)])
            lv = 1
            while queue:
                for _ in range(len(queue)):
                    state, req = queue.popleft()
                    for u in unique:
                        cp, r = state[:], req
                        for k,v in u:
                            val = min(cp[k], v)
                            cp[k], r = cp[k] - val, r - val
                            if not r: return lv
                        nxt = tuple(cp)
                        if nxt not in visited:
                            visited.add(nxt)
                            queue.append((cp, r))
                lv += 1
            return -1
    

Log in to reply
 

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