LeetCode 139. Word Break - Interview Prep Ep 79
Vložit
- čas přidán 9. 07. 2024
- ⭐ Shop on Amazon to support me: www.amazon.com/?tag=fishercod...
⭐ NordVPN to protect your online privacy: go.nordvpn.net/aff_c?offer_id...
⭐ NordPass to help manage all of your passwords: go.nordpass.io/aff_c?offer_id...
Problem link on LeetCode:
Word Break: leetcode.com/problems/word-br...
⭐ Support my channel and connect with me:
/ @fishercoder
Algorithm explained:
We use an extra boolean array of size n+1 to serve as a cache, which means up to position dp[i], it's possible that there is a valid word in the given dictionary to break the string into. We use two pointers to loop through all possible substring breakdowns and store the temporary results into this boolean array called DP to help us cut repetitive computations. In the end, we could just return DP[N].
// TOOLS THAT I USE:
○ Memory Foam Set Keyboard Wrist Rest Pad - amzn.to/3cOGOAj
○ Electric Height Adjustable Standing Desk - amzn.to/2S9YexJ
○ Apple Magic Keyboard (Wireless, Rechargable) - amzn.to/36gy5FJ
○ Apple Magic Trackpad 2 (Wireless, Rechargable) - amzn.to/36ltimu
○ Apple MacBook Pro - amzn.to/30iSvKE
○ All-In One Printer - amzn.to/34etmSi
○ Apple AirPods Pro - amzn.to/2GpVYQf
○ My new favorite Apple Watch - amzn.to/2EIIUFd
// MY FAVORITE BOOKS:
○ Introduction to Algorithms - amzn.to/36hxHXD
○ Designing Data-Intensive Applications - amzn.to/2S7snOg
○ Head First Java - amzn.to/2ScLDKa
○ Design Patterns - amzn.to/2SaGeU2
Follow me on Github for complete LeetCode solutions: github.com/fishercoder1534/Le...
Support me on Patreon: / fishercoder
My ENTIRE Programming Equipment and Computer Science Bookshelf:
www.amazon.com/shop/fishercoder
And make sure you subscribe to my channel!
Your comments/thoughts/questions/advice will be greatly appreciated!
#Kahnsalgorithm #graphsearch #topologicalsorting #softwareengineering #leetcode #algorithms #coding #interview #SDE #SWE #SiliconValley #programming #datastructures
I have two words for you "Monospace font" :) Things will align properly if you use one.
How could anyone come up with this solution without having seen it before
exactly!!!!!!
Interview problems are horrible
No one does, you just have to slug your way through by practising.
if you do it top down you'll see how you get to the bottom up. the problem is all these "DP" videos give you the bottom up first - but the intuition comes from the top down.
All programming interviews expect you to have seen these things before, if you have well and good, you have good enough level to write the code they have already thought or at least debug it. Consider an example of solving such questions in interviews if no programming sites existed, apart from easy and some medium level, majority of the questions would never get solved with an efficient solution
How about converting the list to a set?
Why do we need to "break"? We've already set j < i, j will never exceed i's index, right? I don't get it sorry
why the second change is an optimization?
what is special at running from i-1 to 0 instead of running from 0 to i-1?
@Fisher Coder
HashSet for storing words would optimize it more, right?
No sane person would figure this on their own.
Great work. Am using python but here are some suggestions. Line 15 to be 'break' instead of 'continue' since we are decrementing j, the gap will keep increasing and will keep being larger than the maxLen. Second suggestion is converting wordDict to SET so that you can check the existence of word in constant time in Line 17.
Could you please explain, how did you reach those two optimizations?
why would one use dynamic programming ?
if you draw the state space tree/ recursion tree, you'll find overlapping problems. hence, we need to look into top-
down/memoization OR bottom-up/tabulization techniques.
the same problem solution by GeeksForGeeks, they started with drawing the recursion tree.
we try to avoid the brute force which is O(2 ^n) , which mostly result in Time Limit Exceeded error, by chaching the subproblems results and reuse it.
- the possible approaches to solve this question (from leetcode solution article) :
1- Approach 1: Brute Force { Time Complexity: O(2^n), Space Complexity: O(n) }.
2- Approach 2: Recursion with memoization { Time Complexity: O(n^3), Space Complexity: O(n) }.
3- Approach 3: Using Breadth-First-Search { Time Complexity: O(n^3), Space Complexity: O(n) }.
4- Approach 4: Using Dynamic Programming { Time Complexity: O(n^3), Space Complexity: O(n) }.
Time Complexity O(n^3): there are two nested loops, and substring computation in each iteration
Space Complexity O(n): there is memoization/dp array/HashSet/or whatever DS we use to momize.
Hope this answer your question :) :) good luck :):)
perfect explanation, appreciate you, also the +1 thing
Glad it helped!
hi @ 4:50 why did we decide to increment j..even though we had i was still at "C"
actually, after each move of i, j should move from 0 to i-1.
e.g.
LeetCode
Leet, Cod, Le, etCo, de, ode
Great explanation sir thank you
Glad you liked it
Why in the code you increment j until it reaches i and only then increment i, but in the presentation you increment i first and then at some unclear point you increment j?
Great video and thanks for the explanation! I watched several videos and this is the only one that explained both the logic and the code clearly. Keep uploading more videos!
Glad it helped!
Thanks for your explanation! It would be helpful if the data in the visual explanation was all aligned and spaced evenly. Other than that, I could understand it.
Great suggestion! Thanks!
Sorry, but I did not get it. If possible, would you please explain again, why you are taking boolean array of size n+1 again ?
He is using a dp array - which is a cache for dynamic programming problems, each index means something, example: dp[4] == true, because “leet” (which are the first 4 letters of the input) IS A WORD
Third optimization:
When j counts down from i-1 to 0, the continue in the if statement can be replaced with break.
you are right.
Why did you iterate in such a weird way, can't you just do the regular 2d for loop with the slight change of i
it is more intuitive, i came up with something like that but didn't think about saving checking the previous word existence (Like dp[1]= F, so L doesn't exist)..
It looks like Sliding Window on top of Dynamic Programming.
Good explanation, we can also calculate minLength to optimise along with maxLength
What is the time complexity of this approach? Is it O(n^3) as substring operation takes O(n) time?
yest
great!
This is the simplest explanation I have seen so far, thank you sir
Glad it helped
Best explanation on YT, thanks!
Glad it was helpful!
this person is an example for having both knowledge and no patience/clarity both at the same time , haha
i don't understand your explanation, why are you incrementing i before j? j is nested inside the i loop but you started by looping through i before j??
If you set a few breakpoints and walkthrough the code, you'll have a better sense of the code. Good luck!
Any one also getting exception?
Was using c# in c# substring needs to s.Substring(i, j-i)
thanks
You're welcome!