1
from functools import lru_cache
2
from collections import Counter
3

4

5
class Solution(object):
6
    def minStickers(self, stickers, target):
7
        counter = [Counter(sticker) for sticker in stickers]
8
        n = len(counter)
9

10
        @lru_cache(None)
11
        def dfs(target):
12
            if not target:
13
                return 0
14
            targ_counter = Counter(target)
15
            res = float("inf")
16
            # using sticker[i] if it contains the first letter of target
17
            for i in range(n):
18
                if counter[i][target[0]] == 0:
19
                    continue
20
                s = ""
21
                for j in "abcdefghijklmnopqrstuvwxyz":
22
                    s += j * max(targ_counter[j] - counter[i][j], 0)
23
                res = min(res, 1 + dfs(s)) if dfs(s) != -1 else res
24
            return -1 if res == float("inf") else res
25

26
        return dfs(target)