Stickers to Spell Word - DP Memoization - Leetcode 691 - Python

[@NeetCode]

💡 DP Playlist: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@amyotun]

The best explanation so far. 👍

[@Cloud-577]

this question should be illegal

[@namitsharma9600]

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.

[@priyankasaddival4794]

I love that "Word break with steroids"😂

[@trefoilz7355]

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.

[@alexzheng9841]

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.

[@mingyuli8887]

who designed this problem? To solve this under 45 mins during interview is insane!

[@hydromarlon4168]

Been working on this question for a week best I could do without this video was 65/101 test cases.

[@arcface2casia255]

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.

[@salczar]

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.

[@AymenDaoudi-u6h]

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.

[@alexzheng9841]

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.

[@MrUnemployedYouth]

Who are you mate? you are an absolute beast! thank you!

[@abhinavbhattca]

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

[@purnawirmanhuang5145]

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.

[@syte_y]

I have to say your explanations are so well done!

[@a19970615]

Can I ask how to get the 2^n? I don't get it from video.

[@Terszel]

Thanks for organizing the playlists for easy consumption

[@fragrancias972]

It would be really spicy if you could use sticker pieces of any length, instead of just one character.

[@danielsun716]

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?

[@AviralSrivastava2809]

What a beautoful explanation!

[@strawberriesandcream2863]

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.

[@strawberriesandcream2863]

i got it now. it's because an array can have at most 2^n subsequences.

[@chiamakabrowneyes]

This is the most evil question I've ever seen

[@Yyyyyyyyhhhhh12342]

great explanation

[@rite2riddhi]

dude , you are gold.

[@haozhu6908]

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).

[@doronbaruch665]

Thank you for doing and sharing this. I love your videos.

[@shuoj.2038]

Can you pls start the tag Binary problems? Really appreciated you make the leetcode problem easy to understand.

[@agnesakne4409]

Why is this problem found under category bit masking? What is its relationship to bit masking?

[@alexzheng9841]

leetcode has an official DP solution that uses bit masking, which I don't understand at all...

[@ravalibusetty]

Thank you! This made my day!

[@algorithmo134]

This question is preety hard.

[@user-le6ts6ci7h]

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

[@venkateshtalapally7505]

23:20 hey would you tell why we are going for recursion only first letter of target and stick matches?

[@melissac4872]

so that we can keep the cache size as 2^n

[@aybarskeremtaskan]

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.

[@anandpad]

because at some point, you have to construct the entire target string some way or the other - and in the process you have to use some sticker or the other. So comparing against all characters in the is a bit redundant. lets say the remainT = "ehat" and the stick(s) are example and with (ofc enumerated) => remainT[0] will match the 'e' and you consume the sticker and in that process you get remainT = "ht"... and subsequently in the next call you use the 'with' sticker again. lets say now the order of stick(s) are 'with' and 'example'. at the first iteration you do not use 'with' and then the loop picks 'example'. so the order doesnt matter. hope this explains

[@maverickreal09]

How are 3-dimensional mortals supposed to solve this in an interview?

[@jieli8]

impossible

[@atharvbhagya4317]

you would have to be international grandmaster to be able to come up with solution in 45 minutes.

[@algorithmo134]

@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

[@sanjeev0075]

Can we cache res for dp[t] in order to avoid the duplicate call or this part is not needed ?

[@saksham.malhotra]

Would sorting target reduce the number of hashes generated to memorize

[@learning_hunt8544]

Can you also provide solutions of trilogy innovations coding interview questions?

[@truthSaty]

Am i the only one who thought greedy approach would do ?

[@shaharrefaelshoshany9442]

best

[@naveenprasanthsa3749]

Need string interleaving

[@nirutgupta5894]

100/101 🥲

[@dominic_lee]

mee mo

[@-kurdush]

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

[@venkateshtalapally7505]

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

[@akashjain7378]

Word Break on Steroid 😆

[@dominic_lee]

Solution is now TLE😣