Stickers to Spell Word - DP Memoization - Leetcode 691 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: leetcode.com/problems/sticker...
0:00 - Read the problem
2:21 - Brute Force
10:50 - Memoization
17:41 - Coding Memoization
leetcode 691
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#memoization #dynamic #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
💡 DP Playlist: czcams.com/video/73r3KWiEvyk/video.html
The best explanation so far. 👍
this question should be illegal
I love that "Word break with steroids"😂
Thanks for organizing the playlists for easy consumption
@Neetcode Hi can we cache both remainT and stick we used? I did it like this dp[(remainT, tuple(stick))] = used but it gives me Time Limit exceeded
Thank you for doing and sharing this. I love your videos.
I have to say your explanations are so well done!
Can I ask how to get the 2^n? I don't get it from video.
Can we cache res for dp[t] in order to avoid the duplicate call or this part is not needed ?
Thank you! This made my day!
Been working on this question for a week best I could do without this video was 65/101 test cases.
dude , you are gold.
Thanks, I wasted a whole day on it. Finally submitted it after watching your video. I will not bother going over more optimised solution now.
Can you pls start the tag Binary problems? Really appreciated you make the leetcode problem easy to understand.
Who are you mate? you are an absolute beast! thank you!
23:20 hey would you tell why we are going for recursion only first letter of target and stick matches?
so that we can keep the cache size as 2^n
Actually, we can skip that check (it is a shortcut for a few things); but we also need a way to return infinity if nothing is consumed; to that end:
we could compare if the remainT == t and if so; return infinity to skip that sticker.
thanks for the solution! could someone please explain why the time complexity would be 2^n? it looks like we can make more than 2 choices for every subsequence if there are multiple stickers applicable.
i got it now. it's because an array can have at most 2^n subsequences.
It can be converted as "find the shortest path between target and an empty string". We can then use bfs with a queue or Dijkstra with a min heap.
Pure BFS won't work since it's still O(m^n), where m is the number of stickers and n is the length of the target. BFS outperforms DFS in that it doesn't search beyond the shortest path, but that's not the main inefficiency here. The main problem is that you are repeatedly solving the same subproblems whether you are doing DFS or BFS, which is why you want to cache the result. Also, in BFS, for every path, you need to keep the entire state (e.g., the remaining target), so it's going to consume a lot of memory, which is not recommended for 2^n problems like this.
This can be simplified is one uses Counters for both the target and the stickers. Then it’s a simple matter of subtracting each counter sticker from the counter target. (Cnt1 - Cnt2, not Cnt1.subtract(Cnt2). I was able to solve this in half the code with this technique.
Would sorting target reduce the number of hashes generated to memorize
who designed this problem? To solve this under 45 mins during interview is insane!
Thanks for sharing this solution. I found it much easier to understand compared to the LeetCode's official DP solution.
To improve the performance, you should always sort the characters in the target before caching. For example, building "abab" and "abba" is the same problem, but the way you are doing it now treats them as different problems. If you always sort the characters, you would cache the result as "aabb" and you wouldn't need to recalculate the solution for any combination of the same characters.
Why is this problem found under category bit masking? What is its relationship to bit masking?
leetcode has an official DP solution that uses bit masking, which I don't understand at all...
00:03 Solving the 'Stickers to Spell Word' problem using brute force and memoization
01:52 Implementing brute force and memoization approach to solve the problem
05:20 Choosing the stickers that contain required characters leads to finding the minimum number of stickers needed
07:06 Using caching or dynamic programming can help optimize the solution
10:37 Using memoization, we can optimize the process of finding the target word in a given set of characters.
12:18 We can have two to the n different subsequences of a given string.
15:54 Using dynamic programming to solve the 'Stickers to Spell Word' problem.
17:33 The code involves converting stickers to a hashmap and using dynamic programming to find the minimum number of stickers to create a target string.
20:35 The return value of the dfs function depends on whether the target string can be created from the given stickers
22:12 The remaining portion of the target string can be created using stickers
25:21 The result is calculated by adding the number of extra stickers used to the initial result.
26:58 Understanding and implementing DP Memoization in Python
Can you also provide solutions of trilogy innovations coding interview questions?
if we do not check the 1st one character, like the target is "thehat" at the beginning, we know we can first go to the sticker "with", cause "th" in with. But if we skip th, what I mean is we iterate all characters in "thehat", th is not in "example", but e and a are in "example", so we can go pass the sticker "example" and the remaining target is "thht", then we can go pass the second sticker "example".
So the path gonna be "thehat with using example" -> "thht with using with" -> "ht with using with", then the target is empty. And the result is still 3 stickers.
But in 11:07, @neetcode said we cannot go pass the sticker"example", because the 1st chacter "t" is only in "with".
I think this thought also gonna be work, but why doesn't neetcode take this solution?
This problem is hard to understand when trying to solve it with regular iterative or recursive DP code structures. It's much easier to understand when using a BFS DP structure (iterative level-order traversal).
hmm, i found your solution this time is overly complicated and the discussion as well. It is hard to pinpoint exact things, but i think a couple of things can be improved:
1. in discussion, you went on length to discuss why simply using target is not enough, but later on you kinda contradict your own discussions. Perhaps i didnt understand the context very well, but i felt like you have not fully understood the solution yet thus you were considering a convoluted scenario where target can not be used as the key.
2. you used dfs(target, stick) as the dfs..., which i find a bit unnecessary... It gives the impression it is a 2-d DP, while actually we can think of the problem as 1-d DP, which has dp(target) = 1 + min(dp(target - sticker1), dp(target-sticker2, ...).
3.Lastly, you didn't explain why we have to check remainT[0] not in s is necessary. In fact it is not necessary condition, you will get the solution as well even without these lines. However, this line is super helpful since it can skip some loops by only processing sticker that is a potential candidate. This can be seen as like a heuristic A star technique in search. Missed an opportunity to explain the trick.
When you choose a stikcker you are basically decreasing count of all the same character in the sticker and the target, then what is the need of reducing the frequency at the very start of the recursion it seems like redundant code
This question is preety hard.
This is the most evil question I've ever seen
Hi NeetCode, thanks for this explanation, it really helped, however please there is a small enhancement you can do:
In fact the reason why your solution at the end is showing less performance, it's because you are not benefiting from the memoization correctly. If you debug your solution, you will find that the line 30 is being hit multiple times for the same "remainT". the variable "used" in the line 24 should check first if "dp[remaintT]" is available to not do the work again. The dp check on the line 11 can be removed.
Thanks again.
best
How are 3-dimensional mortals supposed to solve this in an interview?
impossible
you would have to be international grandmaster to be able to come up with solution in 45 minutes.
Need string interleaving
Was asked to solve this in 20 minutes in a Facebook screening call.
Pretty sure the interviewer himself couldn't have done it in 20 minutes (if it was his first time)
It looks like they just expect us to parrot the solutions.
To be honest these interviews are more fake than American porn.
stick[c] -= 1 can anyone please explain what this line is actually does?
does it going to decrease length of each sticker we have passed to function please explain 😑😫😫.I have listened it 5 times still I am getting confused. what its actually doing? please reply me ASAP
Stick is a dictionary which track frequencies of each character. When we deal each sticker with target we are reducing the frequency as we are cancelling the matched ones
100/101 🥲
Am i the only one who thought greedy approach would do ?
mee mo
Word Break on Steroid 😆
Solution is now TLE😣