LC 0691 [H] Stickers to Spell Word - ALawliet/algorithms GitHub Wiki
Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1. (so we need to try different combinations of stickers and find the optimal)
["with","example","science"]
"thehat"
[
Counter({'w': 1, 'i': 1, 't': 1, 'h': 1}),
Counter({'e': 2, 'x': 1, 'a': 1, 'm': 1, 'p': 1, 'l': 1}),
Counter({'c': 2, 'e': 2, 's': 1, 'i': 1, 'n': 1})
]
class Solution:
def minStickers(self, stickers: List[str], target: str) -> int:
# O(n * 2^n) where 2^n is subsets and n is the number of stickers
stickCount = []
for i, s in enumerate(stickers):
stickCount.append(Counter(s))
# stickCount.append({})
# for c in s:
# stickCount[i][c] = 1 + stickCount[i].get(c, 0)
# print(stickCount)
dp = {} # key = subseq of target | val = min num of stickers
def dfs(t, stick): # subseq, 1 sticker at a time
if t in dp:
return dp[t]
# if t == '':
# return 0
res = 1 if stick else 0 # stickers used so far, whether we used the one passed in, and after {} we only pass if first char remainT in s
remainT = ''
# exhaust the current sticker passed in
for c in t:
if c in stick and stick[c] > 0: # target has char in sticker
# used a char from sticker, decrement
stick[c] -= 1
else:
# we did not use, track subseq we were not able to get
remainT += c
if remainT:
used = float('inf') # how many more stickers do we need to complete this remaining portion of the string
for s in stickCount: # go through every other sticker where the first character matches
if remainT[0] not in s:
continue
# we only want to recurse if the sticker choice at least has the first char remaining
used = min(used, dfs(remainT, s.copy())) # s is an object that we modified in stick[c] -= 1 so we should copy into recursion
dp[remainT] = used
res += used
return res
res = dfs(target, {}) # start with an empty sticker
return res if res != float('inf') else -1