Problem statement

https://leetcode.com/problems/stickers-to-spell-word/

Solution 1

Actually, it is very similar to Problem 0638 Shopping Offers if we work with letters frequencies.

Complexity

Time Complexity: O(2^T * S * T), where S is the total number of letters in all stickers, and T is the number of letters in the target word: we have O(2^T) states, S possible steps from each state and O(T) time to generate each of these steps. Note, that we use here also if c[state[0]] == 0: continue line which forces us on each step take sticker which decrease frequency of the smallest letter in our state. In fact it will increase our speed like 10-20 times, because of early stoppings.

Code

class Solution:
    def minStickers(self, stickers, target):
        stickers = [Counter(s) for s in stickers if set(s) & set(target)]
        
        @lru_cache(None)
        def dfs(state):
            if not state: return 0
        
            cnt, res = Counter(state), float('inf')
            for c in stickers:
                if c[state[0]] == 0: continue
                nxt = dfs(''.join([s * t for (s, t) in (cnt - c).items()]))
                res = min(res, 1 + nxt)
            return res
        
        res = dfs(target)
        return res if res != float("inf") else -1

Solution 2

There is a solution, which has the same complexity (there is O(2^T * S) states with O(T) time to check one state), but which works 10 times slower, because of sparsity of our data: in a lot of cases our \texttt{nxt} will be the same as \texttt{state}, but we can not check it quickly in $O(1)$ as we did in previous approach.

Complexity

Is the same as previous, but can work slower.

Code

class Solution:
    def minStickers(self, stickers, target):
        stickers = [Counter(s) for s in stickers if set(s) & set(target)]
        
        @lru_cache(None)
        def dfs(state, q):
            if not state: return 0
            if q >= len(stickers): return float("inf")
            nxt = ''.join([s * t for (s, t) in (Counter(state) - stickers[q]).items()])
            if nxt == state: return dfs(state, q+1)
            return min(dfs(state, q+1), dfs(nxt, q) + 1)
            
        res = dfs(target, 0)
        return res if res != float("inf") else -1

Remark

There is also solution, using binary masks with the same complexity, need to investigate.