STICKERS TO SPELL WORD | LEETCODE 691 | PYTHON DFS + MEMOIZATION SOLUTION
Vložit
- čas přidán 24. 07. 2024
- Channel Discord Community: / discord
Problem Link: leetcode.com/problems/sticker...
Today we are solving a god awful question that is really quite hard. It involves some tricky logic and good knowledge of DFS, memoization, and data structures to solve. It's Stickers to Spell Word (Leetcode 691).
TIMESTAMPS
00:00 Intro
00:07 Question Prompt
00:35 Basic Examples
02:05 Solution Intuition
04:30 Coding
18:00 Time/Space Complexity
19:58 Outro - Věda a technologie
Its fun to listen to your commentary while solving the problem. It makes the learning process more real than just going through another problem solving technique.
LMAO the pain and exhaustion at the end was funny. Great work as always and thanks for going through that for us.
Factual 😂
I asked and you delivered! You're a goddamn legend. Definitely the clearest solution video I've watched on this BS problem. Thank you!
Little note @ 0:50, - example 2 is not possible because none of the stickers contain an "a". Think you just misspoke mentioning "b" there.
Haha thanks, this one was definitely not a fun one to solve!
Thank you for this gem!!!!
Right on time 🙌
the dark theme and zooming in to code is much better thanks
Yea lessons learned! Not going to bother remaking the old ones but agreed it's much easier to see
Love this solution!
Thanks soo much as always
Great Video, I was struggling with this question.
Glad you liked it, was not a fun one for sure
Struggled with this question for a few weeks now. This is definitely the cleanest and most intuitive approach. Thanks for making this video man, really appreciate it!
Also on line 24 - I thought Counters are unordered collections. I am surprised to see that "remaining_characters" counter somehow works here and returns the chars in the same order every time across different target strings (for the memo to work). I was thinking that we would do sort on the keys before constructing the "letters" list.
You know I thought this as well and was surprised it just worked. Maybe it is accepted whether or not you use the sorting. But yea to avoid duplicate work the ordering should always be normalized. But maybe collections.Counter is somehow a sorted dictionary as well
@@crackfaang nice video! Does ordering matter though? Since we are going through all characters anyway. I also wouldn't have thought of just checking the first character. I would have taken a set intersection or something, and that would be linear time for every word. This is cool.
@10:29 ```if target_str[0] not in sticker: continue. ```
I cannot quite follow here. Say target_str = "then", sticker={a:1,e:2, n:2}, we will just skip this sticker because "t" is not in it?
thanks bro, your solution is great first i though of storing used character in mask than found out there may be duplicate characters also
Whenever I see a solution in the discuss tab that involves masking I always just close it lol that shit is too hacky for me
is it safe to assume if they ask me this, they don't want me? Lol
Haha yea it is a tricky one. But just one you memorize and be done with it. As long as you can explain it as you go, it's fine
what is the idea behind ans = min(ans, 1+dfs(target_str))? I dont seem to understand this part.. Why are we checking for the min value?
In the first loop the value of ans will be float('inf').So that makes sense for the first loop. But from the second loop why should it be the min value?
Could you explain why we are skipping the sticker if target_str[0] is not in sticker? I'd struggle to be able to explain my decision for line 19 in an interview.
It would be too expensive to check every single character so we only check the first because it would be a O(1) operation. If we can get a solution, it won't matter in the end because eventually all the characters will be used up.
@@crackfaang if we skipped on a sticker because it did not have the first match, and no other stickers had any matches, then woulnd't it turn out to be not finding out the solution even though it exists?
Do you have github repo for codes you implemented here?
It looks like a linear integer programming problem, something like a knapsack problem? I would definitely throw this thing to a LIP solver such as LINDO.
I think that lines 19 and 20 are a hack for leetcode to speed up specific cases. I don't see any reason why [0] was chosen
why why why why why are we checking just the first character existing and only when it exists do you try dfs? it may have second character or third character? not only this video but also neetcode makes that assumption! omg! second character of the target string might exist in the sticker!!!
what happens if we passed on a sticker that is going to be the only stick that's helpful to progress but we passed on it just because it was not holding the first character?
I don't think you fully understood the algorithm. If we have to check every single character in the string it will be too computationally expensive. The key part here is that if there is a match on the first character of the string we are trying to build with a character in the sticker, we then take ALL the intersecting characters by using the set operations. Thus it saves us from having to check each character individually.
If a solution exists, then doing it with just looking at the first character will eventually give us an answer because we continually take characters in a greedy manner from the sticker until we have matched all the characters. Conceptually it can be hard to see this but I'd recommend doing this problem line by line with a pen and paper and following the code in the video to see how the string changes and how we take characters.
Does this solution not work on leetcode anymore? The code seems to be returning -1 constantly and leetcode is rejecting the solution :((
Here is the code I used..
def minStickers(self, stickers: List[str], target: str) -> int:
sticker_counts = [collections.Counter(stickers) for sticker in stickers]
memo = {}
def dfs(target_str):
if not target_str:
return 0
if target_str in memo:
return memo[target_str]
target_counter = collections.Counter(target_str)
ans = float('inf')
for sticker in sticker_counts:
if target_str[0] not in sticker:
continue
remaining_characters = target_counter - sticker
letters = [char * count for char, count in remaining_characters.items()]
next_target = "".join(letters)
ans = min(ans, 1 + dfs(next_target))
memo[target_str] = ans
return ans
ans = dfs(target)
if ans != inf:
return ans
else:
return -1