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.
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.
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 .
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!
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.
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.
@@kashyapdesai2727 I am getting java.lang.StackOverflowError Truncated error message when using memoization using HashMap. Did anyone else also got the same?
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.
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)
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.
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
Very clear Explanation. Thank you so much :)
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 😋
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 😅
You are very good Nideesh! You don't have to be stressed! Best tutorial with the theory properly explained. Thank you.
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.
Best video Sir... Crystal clear concept,Had been made much confusing by other tutorials.
This is the best explanation I saw for word break problem. Cheers man
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
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!
Hats off! Very well explained, concise and dense.
best explanation on the entire internet
hand down the best explanation
good explanation and one of the very few resource available for word break problem.
Highly appreciate the help !!! Cheers !
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.
Awesome , keep uploading please !!
Thanks for this! Great explanation, really helped me understand the DP solution.
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
Thankyou Nideesh, that was really helpful 😊
Very intuitive, clear explanation, keep it up!
Super well explained! Thank you
Thank you so much for detailed explanation
Nicely explained, very clear. Thanks.
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.
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.
High-quality explanation
Please make this guy do all of your videos...please.
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.
Sir, thanks for this video. I think that list.contains(s.substring(i, len)) should be list.contains(s.substring(i, len-i))
Great explanation, thank you so much :)
Wha's the time and space complexity of the first approach with memoization?
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
Wow man. I feel like I wanna meet you and thank you personally 😆 What an explanation! Kudos
Nice 👍 explanation
nicely explained!
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?
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
very nicely explained
Ossm bro.keep it up..
😎 mighty one 😎
In cpp there should be s.substr(i,len-i) in last method in if condition...
Yep for recursive approach
Superb, thanks!
Thanks Brillian Man!
In the dp approach, why won't we do : "map.put(s, true)", instead of map.put(stringToTest.substring(i, s.length), true))?
How is the run time of the memoized solution O(N^2)
Doesn't anyone have audio lag for the video?
AWESOME!!
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.
Dammm great one
Awesome!!!
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)
You need an amplifier on your voice . I should design you a special one just for your voice. Otherwise, good job and thanks !
why starting from index 1??
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.
Awesome
Why is dp[0] = true?
you can always form a string of length 0 by not choosing any word from the list.
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
O(n^3) right? n^2 for the loops and another n for substring. Can anyone confirm?
right
volume is very slow
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
voice is not clear even after using earphones...!!! 😐😐
Very low audio
Voice not audible at even full volume on earphones.
Han mu me gutkha daba k bol ra aisa lag rha
wow!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1111111
Is he using fake accent ?
should've done coding on machine
True, but coding on whiteboard is what they ask for in interviews
clapss..!!
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.