Word Break Problem | Dynamic Programming | GeeksforGeeks
HTML-код
- Опубликовано: 8 фев 2025
- Find Complete Code at GeeksforGeeks Article: www.geeksforge...
This video is contributed by Nideesh Terapalli.
Please Like, Comment and Share the Video among your friends.
Install our Android App:
play.google.co...
If you wish, translate into local language and help us reach millions of other geeks:
www.youtube.com...
Follow us on Facebook:
/ gfgvideos
And Twitter:
/ gfgvideos
Also, Subscribe if you haven't already! :)
Best explanation. It's so clear. I have watched other videos where they start with a dp matrix but don't explain the intuition behind it. This was an awesome explanation and I am never going to forget it.
can you link the video where they make the matrix first
Look no further folks. At the time of this comment this is by far the best video to watch to learn how to solve this problem because it doesn't immediately jump to an optimized solution without explaining how to get there.
thank you so much... this is the video i am searching for... the best video for this question. hope u could do more videos thank you!
very clear
THIS IS THE BEST EXPLANATION VIDEO! HE CAN EXPLAIN IT FROM THE INTUITION UNTIL THE CODE 🔥🔥 other peole only explain it by jumping to code directly 😅
Very clear Explanation. Thank you so much :)
You are very good Nideesh! You don't have to be stressed! Best tutorial with the theory properly explained. Thank you.
Best video Sir... Crystal clear concept,Had been made much confusing by other tutorials.
hand down the best explanation
Best explanation for DP about wordbreak. thank you very much
What's the time complexity of the final solution, do you know?
@@tommyls4357should be O(n^2) bro
Hats off! Very well explained, concise and dense.
At 16:47 instead of s.substring(i,len) i think it should b s.substring(i , len-i) if u r going for c/c++. actually it depends on how u justify using the second parameter . if u mean the index value then its ok .. but in c/c++ it means the length u want after the index i .
You sir are awesome... Been struggling on this last two hours. Thanks for existing 😋
10:30 You dont really need a map. A set would do. You can assume it always returns false If It finds a sub string you already did.
FABULOUS! Any video can't replace the explanation and conceptual simplicity this video has. TO_THE_POINT CONCEPTUAL VERY_CLEAR. Best video on this question I came across! Really loved it!
This is the best explanation I saw for word break problem. Cheers man
Thanks for this! Great explanation, really helped me understand the DP solution.
good explanation and one of the very few resource available for word break problem.
Highly appreciate the help !!! Cheers !
Thank you so much for detailed explanation
nicely explained!
Super well explained! Thank you
Awesome , keep uploading please !!
static bool DPWordBreak(string s, IList wordDict)
{
int length = s.Length;
bool[] dp = new bool[length + 1];
dp[0] = true;
for (int len = 1; len
best explanation on the entire internet
Brute force approach time: O(2^n) because there are n+1 ways to partition a string of length n and each of the partition can be chosen in 2 ways.
Nicely explained, very clear. Thanks.
Nice 👍 explanation
Wha's the time and space complexity of the first approach with memoization?
In the DP approach, it will be list.contains(s.substring(i,len-i))
depends on language, for java it will work but for c++ it will be len-i
s.substr(a,b), gives a sub string starting from index a and has length b. Note b is not the end index. s.substr(i,length) should be corrected to s.substr(i,len-i). Also why are we considering dp[0] as true? we have available "c" "od", "e", "x", any string of length zero isn't present in the given dictionary.
I think we should run a separate loop for dp[1] instead of dp[0] and then we can start generic loop.
The main intuition is - the word can be broken into two halves [prefix+suffix]. Now we check if prefix exists in the given set and can we break the suffix. Lets say input word is "leet" and the wordset contains ["leet"]. In this case, the word leet can be broken into 2 halves with prefix = leet and suffix = "". now in the next level of computation if we donot return true i.e. "" is also present in the given set then the code will fail. Hence dp[0] is true.
Thanks for the explanation. One thing I am trying to get my head around is why an empty string is considered found in the word dictionary? This pattern is seen in many dp problems and I am really confused about it.
I was confused about it as well. After some thought, I've concluded that the empty string being considered found is misleading. dp[0] = true is used to simplify how the solution looks. I was able to solve this problem with a dp array of s.length(), but the solution GeeksForGeeks presents is a little cleaner than mine, since you don't have to subtract the index by 1 or check if the index is 0.
Very intuitive, clear explanation, keep it up!
There is some issue with the memoization code, it takes more time than the normal recursive approach.
You are putting in the map after the recursion call, so when recursion happens, map is still empty.
if (set.contains(s.substring(0, i)) && wbMemo(s.substring(i, s.length()), set, map, count)) {
map.put(s.substring(i, s.length()), true);
Let me know your thoughts.
Thankyou Nideesh, that was really helpful 😊
High-quality explanation
Sir, thanks for this video. I think that list.contains(s.substring(i, len)) should be list.contains(s.substring(i, len-i))
Please make this guy do all of your videos...please.
Simply Amazing, the best explanation came across for this question. Thanks, Man!
I cant hear well even at max volume. But it's good to understand. thanks.
very nicely explained
Great explanation, thank you so much :)
any other videos by this person? he's brilliant + the accent too
check his youtube channel. he is brilliant in addressing the intuition!
Just amazing, thanks dude
Ossm bro.keep it up..
AWESOME!!
Wow man. I feel like I wanna meet you and thank you personally 😆 What an explanation! Kudos
Thanks Brillian Man!
😎 mighty one 😎
In cpp there should be s.substr(i,len-i) in last method in if condition...
Yep for recursive approach
In the dp approach, why won't we do : "map.put(s, true)", instead of map.put(stringToTest.substring(i, s.length), true))?
Can anyone tell me which category of DP does this question comes under? Looks to be a variation of a knapsack problem? Correct me if I am wrong.
Superb, thanks!
Awesome!!!
Dammm great one
It should be s.substr(i,len-i) in the final code
Correct..good catch
s.substr(s,len) works fine...
@@kashyapdesai2727 I am getting java.lang.StackOverflowError Truncated error message when using memoization using HashMap. Did anyone else also got the same?
How is the run time of the memoized solution O(N^2)
Hi Nideesh, I have a basic question. Will you solve all these questions without looking into the answer every time? I face a lot of problem trying to do these questions for the first time :O
Try to practice all questions on data structures . Once you complete it repeat the cycle. On your 4th cycle you will definitely be able to solve 90% questions and further many new questions. Thank you 😊
How will you get "CO" and Recursion of (DE) ? You are doing recursion of DE only if CO is in dictionary and CO does not exist. once you find C in dictionary you dont try "CO" You try ODE.
The recursion happens only for
"code"
"ode" ( since C is in dictionary)
"e" ( since OD is in dictionary) .I am confused. The whole premise of memoization is based on repeating recursion which I dont see happening.. can someone explain.
Very good video
Can someone please help me to understand space complexity in case of memorisation approach ? I think that is exponential
Dark Knight memoization cannot be exponential as you donot calculate the solution of an already calculated sub problem again and again. Space complexity would be o(n) and time complexity is 0(n)
Awesome
Doesn't anyone have audio lag for the video?
This is an O(n**2) solution right? there is a O(n*s) one where s is the max word length.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDict=set(wordDict)
maxLen=0
for i in wordDict:
maxLen=max(len(i),maxLen)
wordStart={0}
for i in range(len(s)):
temp={i for i in wordStart}
for j in wordStart:
if i-j +1 > maxLen:
temp.remove(j)
elif s[j:i+1] in wordDict:
temp.add(i+1)
wordStart=temp
return True if len(s) in wordStart else False
This is my code.
why starting from index 1??
Why is dp[0] = true?
you can always form a string of length 0 by not choosing any word from the list.
You need an amplifier on your voice . I should design you a special one just for your voice. Otherwise, good job and thanks !
Your recursion/dfs will not pass on LeetCode
@@mohdzebalam8706 I am discovering it' s better to stay away from Java substring() method
@Mohammed Zeb Alam Time Limit exceeded which, I think is caused by the inefficient substring() method
volume is very slow
Very low audio
working on leetcode,
memoization,
map dp;
bool WordBreakmem(string s, vector& wordDict){
if(s.size() == 0)
return true;
if(dp.find(s) != dp.end())
return dp[s];
for(int i = 1; i
O(n^3) right? n^2 for the loops and another n for substring. Can anyone confirm?
right
wow!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1111111
voice is not clear even after using earphones...!!! 😐😐
clapss..!!
Is he using fake accent ?
Voice not audible at even full volume on earphones.
Han mu me gutkha daba k bol ra aisa lag rha
should've done coding on machine
True, but coding on whiteboard is what they ask for in interviews
confused guy
khana khaye bina vdo bna rha h kya broo.. Thoda energetic raha kro yr.
can you speak a bit louder and clear?
Use CC/subtitles if you can’t comprehend. He was pretty clear.