9 lines Python


  • 0

    Cover the smallest target character by any word containing it, and cover whatever is left recursively. Use memoization for speed. Gets accepted in about 1000 ms (I think 2000 ms are allowed).

    def minStickers(self, stickers, target):
        if set(target).difference(*stickers):
            return -1
        def ms(target, memo={(): 0}):
            key = tuple(sorted(target.elements()))
            if key not in memo:
                memo[key] = 1 + min(ms(target - s) for s in stickers if min(target) in s)
            return memo[key]
        stickers = map(collections.Counter, stickers)
        return ms(collections.Counter(target))
    

    It's faster to determine the smallest character only once. Then it takes about 830 ms:

    def minStickers(self, stickers, target):
        if set(target).difference(*stickers):
            return -1
        def ms(target, memo={(): 0}):
            key = tuple(sorted(target.elements()))
            if key not in memo:
                c = min(target)
                memo[key] = 1 + min(ms(target - s) for s in stickers if c in s)
            return memo[key]
        stickers = map(collections.Counter, stickers)
        return ms(collections.Counter(target))
    

    It's even faster to instead use the character that occurs in the fewest stickers. Gets accepted in about 650 ms:

    def minStickers(self, stickers, target):
        if set(target).difference(*stickers):
            return -1
        def ms(target, memo={(): 0}):
            key = tuple(sorted(target.elements()))
            if key not in memo:
                c = min(target, key=lambda c: sum(c in s for s in stickers))
                memo[key] = 1 + min(ms(target - s) for s in stickers if c in s)
            return memo[key]
        stickers = map(collections.Counter, stickers)
        return ms(collections.Counter(target))

Log in to reply
 

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