Bro. You made my day. I was exhausted by this problem and couldn't find a correct explanation. Your dry runs and explanation were way too smooth. Thank you so much.
Hello all, I've actually made a few mistakes in this video as many kind viewers have pointed out. I just want to note them here. 1) For the bottom up approach it would have been a good idea to convert the dictionary to a set first. This allows us to look up values in O(n) time. O(n) and not O(1) because in order to compute the hash for the string you have to go through the string char by char. 2) For time complexity of the bottom up and top down approach. Those should be O(n^3) technically (if we use a set for bottom up). It is because implicitly it cost O(n) to compare strings in the worst case (again because of the cost of computing the hash). 3) Furthermore the memoization solution should be O(N^2) space complexity as implemented, because we are storing the whole string; however, it is possible to come up with an O(N) space by simply storing a true false array corresponding to the string. Where memo[i] would be s[i...] subproblem can be solved. If you have any further questions or see more mistakes feel free to let me know. Sorry again for the mistakes and any confusion that I might have caused. I was counting things weirdly in my head at the time of making this video haha.
@Knapsak - for top down with memoization, shouldn't the time complexity be O(d * N^3)? As we saw, there can be N^2 unique recursive calls. For each call, we iterate over (potentially in worst case), all words from given dictionary - so the for loop runs at the most d times (d = length of Dictionary) - And for each of those d iterations, we do string slicing s[0:len(x)] - which in worst case takes O(N) time. Thus, for each of the N^2 recursive calls, we do O(d*N) amount of work. So the time complexity should be O(d * N^3), right? Can you please point out if I am missing something here? Thanks !!
it might not work for overlaping dict string like s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] from leetcode i tried it it is not working please sugget me a solution for bottom up approch
Hello Mr.Knapsack...I think you are doing a great job and your explanations are crystal clear. Please make more such videos on DP with both recursive, top-down and bottom-up approaches as you have done till now.
I really like the way you dry run the recursive brute force method. Thanks for doing this. It was really helpful in understanding. Please keep doing dry run with example in your future videos too. Please keep them coming, and thanks again for high quality content.
An excellent explanation and nicely presented too. Thumbs up for that. I do however a query. using brute force approach ....for the 4th example @0:50 where dict = [ "rac", "fast", "car", "racecar"] after the first iteration, "fast" will be removed and s becomes "racecar". the word "rac" is then used which makes s = "ecar" and this makes the result as false. I think im missing something here and would really appreciate if this could be explained - thanks alot!
@Knapsak For the top down memoization solution, I don't understand why the space complexity is O(N); If we take your example of "abcd" at 9:33, I believe the memoized dictionary should contain the following subproblems: ['a', 'b', 'c', 'd', 'ab', 'bc', 'cd', 'abc', 'bcd', 'abcd']. If there are N^2 unique subproblems, then how is it we're using O(N) space worst-case?
Yeah you are right my mistake. I was counting a single string as O(1). I think the subproblems are from a position to the end of the who string so for example. "abcde" would be ["bcde", "cde", "de", "e"] regardless still O(n^2). Sorry again for the mistake.
Best explanation!! Pls make more videos like this :)) It would be nice if you also provide a link from where you took this problem(like leetcode, hackerrank etc)
Thank you so much for this its really helpful with all these editing. I had the same approach its just i could figure out how to implement memoization. Those posts on leetcode discuss dont help at all they all just show code and try to explain in 2 sentances :S
How is top-down runtime polynomial? Shouldn't it be linear since there's only one for loop with early returns for recursion over already computed subproblems?
For the bottom up approach, can you share the intuition of how to come up with a decreasing j? Would an increasing j also work? it seems to me that yes. As at the end we would be asking if we can solve the subproblem [0...j] and string [j+1, ... i] being in the dictionary. And increasing j or decreasing it, seems to yield the same generic question. Or is there a reason of why to choose a decreasing j ? For me, it makes it look as in "harder" to come up with.
Nice explaination, but I think dictionary would not be necessary for memoization and neither passing string U can use just index for recursive solution
really good explanation! i was able to come up with the top down solution but i had trouble figuring out what the subproblems meant and just kind of got lucky with my thinking, but after the example you gave showing the duplicate subproblems, i think it makes more sense. for each subproblem, you ask "with the current string s(which may be a substring of the original input string), can i make this string using the other strings in the dictionary". does that sound right?
sir i have a question.... at 15:19 in bottom up approach, you have mentioned that for i=2, j=0, s[j:i]='ab' But in list slicing, the list should be sliced from j(0) to i-1(2-1=2) so it must be 'a'... please answer
Hello so I think where the confusion is coming from is distinguishing between the DP table and the string itself, notice the the corresponding values in the DP table are "shifted" by one to accommodate for the empty string base case. The string itself, s[0] = 'a', and s[2] = 'c'. Therefore when j=0 and i=2, s[j:i] = s[0:2] = 'ab'. Hope this clears things up! Feel free to follow up if there is still confusion! :)
Can we say that the top down algorithm is O(N^3) because the for loop is O(N), and the substring processing(s[0:len(x)) also costs O(N), making the code inside the helper function O(N^2), but because it's recursive we multiply that by the for loop which is O(N), resulting O(N^3)?
@@KnapsackLabs Hey bro no worries, I've seen your pinned comment but even with that I wasn't able to fully understand the time complexity of the algorithm because of the for loop + a recursion inside of it. Thank you for the great content btw, explained details like your videos are extremely rare.
This is a hard question to answer! I would say there isn't really any set way of knowing if a problem needs a 1d vs 2d dp table. Usually when I'm solving these problems, my general approach is to start with the recursive solution or the recurrence relationship. From there I ask myself "can I represent the subproblems in a 1d table or am I going to need more space with a 2d table" and usually I can figure it out from there. So my advice would be don't start with the dp table, start with solving the recurrence relationship and figuring out how the problem can use previous subproblems to solve the current one. You can then see if the previous subproblems you need can fit in a 1d array or if you need more space and need to instantiate a 2d array. Hopefully this helps!
I'm currently finishing my last year in college. I've done internships and will be starting full time at some of the larger tech companies. I don't want to say exactly which ones but they are among Facebook, Amazon, Apple, Microsoft, and Google.
Hi sorry there is no link to code at the moment. I'm working on making a website to display this; however, I've been delayed because I'm actually preparing for the interview process myself. I hope to have it up in a couple months. I apologise once again.
This problem is solved with multiple variants with one DP approach having O(N*S) where S is the length of the max string in the dict. I didn't understood the approach here www.geeksforgeeks.org/word-break-problem-dp-32/ and came to your video. The bottom-up approach resulted in O(N^2) in your solution. Can you have a look to the solution in the link? Thanks
Spent 3 days searching for a good video explanation....and then found this....great and simple explanation....thank you:)
Bro. You made my day. I was exhausted by this problem and couldn't find a correct explanation. Your dry runs and explanation were way too smooth. Thank you so much.
Hello all, I've actually made a few mistakes in this video as many kind viewers have pointed out. I just want to note them here.
1) For the bottom up approach it would have been a good idea to convert the dictionary to a set first. This allows us to look up values in O(n) time. O(n) and not O(1) because in order to compute the hash for the string you have to go through the string char by char.
2) For time complexity of the bottom up and top down approach. Those should be O(n^3) technically (if we use a set for bottom up). It is because implicitly it cost O(n) to compare strings in the worst case (again because of the cost of computing the hash).
3) Furthermore the memoization solution should be O(N^2) space complexity as implemented, because we are storing the whole string; however, it is possible to come up with an O(N) space by simply storing a true false array corresponding to the string. Where memo[i] would be s[i...] subproblem can be solved.
If you have any further questions or see more mistakes feel free to let me know. Sorry again for the mistakes and any confusion that I might have caused. I was counting things weirdly in my head at the time of making this video haha.
@Knapsak - for top down with memoization, shouldn't the time complexity be O(d * N^3)?
As we saw, there can be N^2 unique recursive calls.
For each call, we iterate over (potentially in worst case), all words from given dictionary - so the for loop runs at the most d times (d = length of Dictionary)
- And for each of those d iterations, we do string slicing s[0:len(x)] - which in worst case takes O(N) time.
Thus, for each of the N^2 recursive calls, we do O(d*N) amount of work. So the time complexity should be O(d * N^3), right?
Can you please point out if I am missing something here? Thanks !!
it might not work for overlaping dict string like s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] from leetcode i tried it it is not working please sugget me a solution for bottom up approch
literally THE best explanation i've seen
After hours of searching for the solution, this came through for me
I am waiting for your next upcoming videos playlist . Please continue this series
One of the best solutions to this problem. Amazing step by step explanation!
Hello Mr.Knapsack...I think you are doing a great job and your explanations are crystal clear. Please make more such videos on DP with both recursive, top-down and bottom-up approaches as you have done till now.
I support this
Amazing explanation! You should post more
trueeeeee
I really like the way you dry run the recursive brute force method. Thanks for doing this. It was really helpful in understanding. Please keep doing dry run with example in your future videos too.
Please keep them coming, and thanks again for high quality content.
An excellent explanation and nicely presented too. Thumbs up for that. I do however a query. using brute force approach ....for the 4th example @0:50 where dict = [ "rac", "fast", "car", "racecar"] after the first iteration, "fast" will be removed and s becomes "racecar". the word "rac" is then used which makes s = "ecar" and this makes the result as false. I think im missing something here and would really appreciate if this could be explained - thanks alot!
@Knapsak For the top down memoization solution, I don't understand why the space complexity is O(N);
If we take your example of "abcd" at 9:33, I believe the memoized dictionary should contain the following subproblems: ['a', 'b', 'c', 'd', 'ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'].
If there are N^2 unique subproblems, then how is it we're using O(N) space worst-case?
Yeah you are right my mistake. I was counting a single string as O(1). I think the subproblems are from a position to the end of the who string so for example. "abcde" would be ["bcde", "cde", "de", "e"] regardless still O(n^2). Sorry again for the mistake.
@@KnapsackLabs No problem! First time coming to the channel / your videos. Thanks for making this video, it was very helpful!
perfect explanation of word break problem .. understood the algo completely
Best explanation!! Pls make more videos like this :))
It would be nice if you also provide a link from where you took this problem(like leetcode, hackerrank etc)
Thank you very much, this is the only video out of so many that I watched which actually helped me understand how to solve
Nice video
You should do many more, definitely the best explanation on youtube for this problem and you just earned a subscription.
Your videos are really awesome dude !!
Best demonstration! Hats off, keep posting , extremely helpful, Master class!!!
This is the best explanation I've seen of this problem! Thank you so much for this wonderful video!
excellent video
you nailed it, keep doing man!
great explaination !! Thanks a lot
Thank you so much for this its really helpful with all these editing. I had the same approach its just i could figure out how to implement memoization. Those posts on leetcode discuss dont help at all they all just show code and try to explain in 2 sentances :S
Simply Awesome! What a presentation!
Can you please create the video for the extension of this problem Word Break II Leetcode 140
great explantation thanks
great explanation! best word break solution breakdown
I'm glad you found it helpful!
Awesome work done ✅ Best explaination I can found online for this problem 💯 Thanks for sharing with us 😁
How is top-down runtime polynomial? Shouldn't it be linear since there's only one for loop with early returns for recursion over already computed subproblems?
awesome, thank you so much, please keep making videos
Very nice explanation. Thank you.
amazing work , well explained , good job
Great explanation. Thank you so much
the best explanation I found on this problem. thank you
Thanks for the explanation buddy! You rock.
nice video, clear explanation along with time complexity, liked and subscribed!
Thank you!
Good implementation. It would be helpful if you explained how you came up with the time complexity. You just say what it is without explaining.
Great explanation, thanks!! 👍
amazing solution
Thanks fo wonderful explanation
For the bottom up approach, can you share the intuition of how to come up with a decreasing j? Would an increasing j also work? it seems to me that yes. As at the end we would be asking if we can solve the subproblem [0...j] and string [j+1, ... i] being in the dictionary. And increasing j or decreasing it, seems to yield the same generic question.
Or is there a reason of why to choose a decreasing j ? For me, it makes it look as in "harder" to come up with.
Nice explaination, but I think dictionary would not be necessary for memoization and neither passing string
U can use just index for recursive solution
really good explanation! i was able to come up with the top down solution but i had trouble figuring out what the subproblems meant and just kind of got lucky with my thinking, but after the example you gave showing the duplicate subproblems, i think it makes more sense. for each subproblem, you ask "with the current string s(which may be a substring of the original input string), can i make this string using the other strings in the dictionary". does that sound right?
Thanks a lot dude ,what a explanation, i am able to solve the question
Glad you found it useful!
sir i have a question.... at 15:19 in bottom up approach, you have mentioned that for i=2, j=0, s[j:i]='ab'
But in list slicing, the list should be sliced from j(0) to i-1(2-1=2) so it must be 'a'...
please answer
Hello so I think where the confusion is coming from is distinguishing between the DP table and the string itself, notice the the corresponding values in the DP table are "shifted" by one to accommodate for the empty string base case. The string itself, s[0] = 'a', and s[2] = 'c'. Therefore when j=0 and i=2, s[j:i] = s[0:2] = 'ab'. Hope this clears things up! Feel free to follow up if there is still confusion! :)
@@KnapsackLabs thanku sir ....no confusions now...clear now
@knapsak minor improvement in runtime if put break after dp[i]=True statement.
Can we say that the top down algorithm is O(N^3) because the for loop is O(N), and the substring processing(s[0:len(x)) also costs O(N), making the code inside the helper function O(N^2), but because it's recursive we multiply that by the for loop which is O(N), resulting O(N^3)?
Yup thanks for noticing, if you look at the pinned comment, I explain my mistake and make the correction.
@@KnapsackLabs Hey bro no worries, I've seen your pinned comment but even with that I wasn't able to fully understand the time complexity of the algorithm because of the for loop + a recursion inside of it. Thank you for the great content btw, explained details like your videos are extremely rare.
Thanks
Trie with memo might be better for this problem
I enjoyed this video.
Hey man! Great video. Just one doubt. how to decide which to use 2d matrix or 1d for dp
This is a hard question to answer! I would say there isn't really any set way of knowing if a problem needs a 1d vs 2d dp table. Usually when I'm solving these problems, my general approach is to start with the recursive solution or the recurrence relationship. From there I ask myself "can I represent the subproblems in a 1d table or am I going to need more space with a 2d table" and usually I can figure it out from there. So my advice would be don't start with the dp table, start with solving the recurrence relationship and figuring out how the problem can use previous subproblems to solve the current one. You can then see if the previous subproblems you need can fit in a 1d array or if you need more space and need to instantiate a 2d array. Hopefully this helps!
@@KnapsackLabs Thanks a ton! You cleared my doubts
where are you working or worked?
I'm currently finishing my last year in college. I've done internships and will be starting full time at some of the larger tech companies. I don't want to say exactly which ones but they are among Facebook, Amazon, Apple, Microsoft, and Google.
Best
Solution is wonderful but where is the link to code?
Hi sorry there is no link to code at the moment. I'm working on making a website to display this; however, I've been delayed because I'm actually preparing for the interview process myself. I hope to have it up in a couple months. I apologise once again.
Great !!!!...
This problem is solved with multiple variants with one DP approach having O(N*S) where S is the length of the max string in the dict. I didn't understood the approach here www.geeksforgeeks.org/word-break-problem-dp-32/ and came to your video. The bottom-up approach resulted in O(N^2) in your solution. Can you have a look to the solution in the link? Thanks
I tried looking at the solution in the link, and I also can't figure out what it is doing. Sorry I couldn't be of any help, best of luck!
Day 37 of trying to understand DP tabulation. Result: I'm not getting any closer to reaching my goal of "getting it"