691. Stickers to Spell Word - cocoder39/coco39_LC GitHub Wiki

691. Stickers to Spell Word

start with target, iterate through stickers, check how much each sticker can contribute. Using recursion to calculate how many stickers is needed if this specific sticker is selected. compare all results at this layer and select the min one.

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        sticker_count = [collections.Counter(sticker) for sticker in stickers]

        @lru_cache(None)
        def dfs(rem):
            if not rem:
                return 0
            
            rem_count = collections.Counter(rem)
            res = float('inf')

            for sticker in sticker_count:
                if all(rem_count[ch] == 0 for ch in sticker):
                    continue
                
                new_rem = []
                for ch, cnt in rem_count.items():
                    if cnt > sticker[ch]:
                        new_rem.extend([ch] * (cnt - sticker[ch]))
                
                use_sticker = dfs(''.join(new_rem))
                if use_sticker != -1:
                    res = min(res, 1 + use_sticker)
            
            return res if res != float('inf') else -1

        return dfs(target)