bro the thing i like most about your channel is that you tell the question from scratch so that viewer doesnt have to go and watch other related videos keep going and make videos this is your greatest strength that one can learn everything about a question from your channel without any need to watch full playlist
I don't know char 'd' of dynamic programming but the way you explain is really appreciable. One of the best channels for a noob to intermediate to understand the concepts. When you say trust me it isn't a medium proble I trust you!! Thank You :)
Very helpful explaination of this question with detailed dry run and pseudocode. I had watched your videos for other Qs too. They are really very helpful. Thank you very much sir.👍
for me this was new question but you made me understand me very nicely......First we just have to think about the recursion then memoization is very easy
I was struggling in this question for some long.. but now by just watching your explanation I solved it myself....... Thankyou soo much for your wonderful explanation❣
I really appreciate each and every thing about you brother....the way you explain every thing from scratch is just awesome. No one really explains that much. Loved your explanation.♥
BRO THANKS TO YOU SINCE YOU ARE THE ONLY PERSON ON THE INTERNET WHO COULD EXPLAIN THIS QUESTION :- ALL POSSIBLE FULL BINARY TREES. NOW I WAS ABLE TO SOLVE TODAYS QUESTION ON MY OWN
Hi Dhairya, You made my day . My video is being uploaded and I mentioned there that try the similar problem and you already did that. I am so proud and happy. Thanks a lot for sharing 😇🙏
@@codestorywithMIK another thing bhiya what if it says all possible trees. Then how do we deal with that since we dont care about all elements less than n in that case
In that case, we will choose every possible node as the left and right subtree. For every i, We can make the left subtrees from (start , i-1) as well as (i+1, end) And similar for right subtrees
Hats Off to you, no one has explained like this. Such a crisp and clear explanation, which is indeed a need for interview preparation. Keep doing this good work🔥✨🙌
Guru ji pranam🙏🏻 I'm soo grateful i found your channel everybody tells the approach and the logic behind the questions but the way you taught using a proper structure or blueprint of how to structure your code is commendable thank you soo much......bhagwap aapko tarraki de🎉
Tabulation code. Class solution { Public boolean word Break(string s,listword Dict){ Setdict= new Hash Set(word Dict); int n=s length (); boolean []dp = new boolean (n+1); dp(0)=true; for(int i=1;i
Thank you so much for the explaination, you made it very easy to understand🙏🙏 One question, are we considering the time complexity for searching the word in the unordered set? Also, could we have used map instead?
true bro striver ke baad sbse shi expalnation aapka lga bro please continue posting videos it help alot way i like is you also explained minor things that other youtuber dont do they just try to finish the video in small length but you also explaoned the doubt portion of student that why that memset is there, why for loop is there in recurssion and many more
Actually i try to complete before my office. Because after office I get really occupied in gym, swimming, sports etc. so it’s better for me to upload early 😊 Thank you again for watching my channel 😇
Thanks a lot for such a clear explanation sir. I just had one doubt that why are we using unordered_set here what will happen if we check by using for loop?
One thing left to be explained,why should we memoise it? From the initial inspection, it looks like there are no common subproblems. Then how come memoise help? I am sure there is an explanation for it but missed in the video. However I liked the video overall. Mostly nobody goes through the process of thinking upfront before solving the problem. So that gives an illusion that the problem might be simple. You took it slow and explained all the gotchas very well. Thank you very much for this video.
let say text=aaaab and we have dict= a, aa, aaa, aaaa. now we divide text one by one see a, yes it is present in dict so we have divide, a aaab similarly after 4 call we have divided, a a a a b but b is not present in dict so, return false means one back step at, a a a ab but ab also not present so return false a a aab aab, now tried to divide here a a aa b, aa is present so we call for '"b' it will return false because of dp so now we tried to divide like this, a a aab, but aab is also not present so return false. so going back we tried to divide like this, a aa ab, aa is present so call for ab, but for ab dp has false from before, so return false; so going back we tried to divide like this, a aaa b, aaa is present so call for b, but for b dp has false so return false so going back we tried to divide like this, aaaa b, aaaa is present so call for b, same story, so going back we tried to divide like this aaaab, but it is not present so return false now finally we return false as loop over.
You make every problem easy to understand. Thanks for the simple explanation. But I couldn't understand memoization in your video, like why indices are memoized. So I stored strings and if they are broken down to dictionary words. My Java code below(memoized in a little different way): class Solution { Map dp; public boolean wordBreak(String s, List wordDict) { dp = new HashMap(); Set dict = new HashSet(wordDict); return solve(s, dict); } public boolean solve(String s, Set dict) { if(dp.containsKey(s)) return dp.get(s); if(dict.contains(s)) return true; for(int i=1;i
Thank you so much Ravi. Actually in recursion, most we memoize the parameters which are changing in every recursive call. If you notice, idx was the only thing which was changing and hence I memoized idx.
@@codestorywithMIK yes I understood that but I couldn't make sense memoizing idx. Like in the tree diagram we see repetitive problems being memoized, so just want to understand from that perspective.
I got your point . Actually I thought it in this way, For a given idx, we will be looking at the substring s[idx, n] for different length 1,2,..n etc and if already it has been solved in some other path, we return.
Shouldn't we pass the modified string i.e the second part of the string in the solve function inside for loop ?? Or shouldn't we check the string from idx to end in the base case ?? Like this => bool solve(int idx,string &s,int n){ if(idx>=n){ return true; } //Here in this part, we need to check the string from idx to end right ?? Else what is the use of passing and checking the same string in each recursive call ? string temp = s.substr( idx , n - idx ); if( st.find(temp) != st.end() ){ return true; } for(int l=1;l
at 23:58, it is necessary to check the greater than condition because you are not putting a check on whether idx+l goes out of bound or not in the recursive call. Btw, badhiya explanation, mza agya
Thanks brother for making a tutorial on word break. ❤❤❤❤ You should launch a DSA course your explanation is superb. May I know where product based company you work for.
the code is wrong in the second base case you should have written if(st.find(s.substr( idx , n - idx )) != st.end()) { return true; } instead of if(st.find(s)!=st.end()){ return true; }
Bhai ye apne for loop bata diya lekin mujhe yaad hai 2nd year mein tha 2022 mein 4 din mujhe lag gaye for loop kese work karta , kyuki koi video nhi thi uss time youtube pe
Hi, Since in the recent videos you have been solving same prob using DP in diff vid. Can you please add the link for same problem using DP in the comments please. Many thanks, and as usual love your vids
Just adding 1 point. Here it's not a concept of taking one time, and not taking the other time, Here we have to take it, if it doesn't work, then keep it, and go on taking the next ones along with the previous ones until we found a matching pair.
class Solution { int [] dp; boolean solve(String s, int idx, Set set) { if (idx == s.length()) return true; if (dp[idx]!=-1) return dp[idx]==1; for (int i = idx; i < s.length(); i++) { if (set.contains(s.substring(idx, i + 1)) && solve(s, i + 1, set)) { dp[idx]=1; return true; } } dp[idx]=0; return false; } public boolean wordBreak(String s, List wordDict) { dp = new int[s.length()]; Arrays.fill(dp,-1); Set set = new HashSet(wordDict); return solve(s, 0, set); } }
Bhai you should start teaching at scalar or crio. You have very good teaching skills also + you are working at a good product based also. So you can guide students in the right direction + extra monetary benefits. Just a suggestion :D
Hi Tanuj, Actually I have been getting offers from many paid platforms (I cant take name here), but there are few things which stop me from going ahead : 1) They want me to make videos by their names. i.e. no more codestorywithMIK 2) They want me to upload videos based on their plan. BUT, i always post videos based on my Subscribers’ needs. 3) They want me to advertise their platform in my videos. I personally don’t prefer promoting paid platforms (who charge big fees) 4) They will charge huge fees for courses that I will make as per their plan. I can’t charge Blindly huge fees. This is the reason I never promote any paid platform in my videos even after getting offer from them. Please share your points and suggestions also. I would love to hear 🙏❤️
@@codestorywithMIK Bro I do agree with you. I mean it takes balls to be take such decisions and avoid offers of such already established names. Actually worst part is all the good creators know that theses platforms are useless, creators like you and many others who are having maybe 500k+ subs learnt DSA on their own (mostly) and using free resources. There is guy ***ver who has all my respect as he is an amazing DSA teacher plus for the things he achieved but then in the videos he promotes useless online platforms which is not good tbh as it is misguiding for under confident students as they would do anything if placements are near, ending up wasting their money and time even though they can learn from channels like yours for free. But from a youtuber's pov, it is not wrong to do such promotions. Actually, you earned it through your hardwork that companies are offering you things. At the end of the day, its your money. 10 years down the line, no one would remember if they studied for free from codestorywithMIK or physics wallah or anywhere else, all they would remember is that they worked hard to gain it. So its totally your call.
if someone having diffculty understanding how memorization save time here, see this let say text=aaaab and we have dict= a, aa, aaa, aaaa. now we divide text one by one see a, yes it is present in dict so we have divide, a aaab similarly after 4 call we have divided, a a a a b but b is not present in dict so, return false means one back step at, a a a ab but ab also not present so return false a a aab aab, now tried to divide here a a aa b, aa is present so we call for '"b' it will return false because of dp so now we tried to divide like this, a a aab, but aab is also not present so return false. so going back we tried to divide like this, a aa ab, aa is present so call for ab, but for ab dp has false from before, so return false; so going back we tried to divide like this, a aaa b, aaa is present so call for b, but for b dp has false so return false so going back we tried to divide like this, aaaa b, aaaa is present so call for b, same story, so going back we tried to divide like this aaaab, but it is not present so return false now finally we return false as loop over.
Backtracking : TLE class Solution: def helper(self,index,s,words,l): if index==len(s): print(l.copy()) return True flag=False for length in range(1,len(s)+1): substring=s[index:index+length] if substring in words: flag=flag or self.helper(index+length,s,words,l+[substring]) return flag def wordBreak(self, s: str, wordDict: List[str]) -> bool: l=[] return self.helper(0,s,set(wordDict),l) My observation while partitioning we can just partition with the minimum length element in the words dictionary Example: s=codestorywithmik words=["code","story","with","mik"] we dont need to partition for all the length from 1 to len(s) we can just take smallest word in words which is "mik" so conclude the length from 3 to len(s) This is a small optimization for backtracking Hope this helps :) class Solution: def helper(self,index,s,words,l,mini): if index==len(s): print(l.copy()) return True flag=False for length in range(mini,len(s)+1): substring=s[index:index+length] if substring in words: flag=flag or self.helper(index+length,s,words,l+[substring],mini) return flag def wordBreak(self, s: str, wordDict: List[str]) -> bool: l=[] mini=min([len(i) for i in wordDict]) return self.helper(0,s,set(wordDict),l,mini)
Sir apne jo st.find(s)!=st.end() lagai hai uska kya fayda hai......kyu sir s ki value to same hi rehri hai .....kya s.substr se s ki length choti hori hai.......koi btao plz
thanks for the explanation. i was able to figure out this one easily. here is my soln: /** * @param {string} s * @param {string[]} wordDict * @return {boolean} */ var wordBreak = function (s, wordDict) { const set = new Set(wordDict); const dp = Array(301).fill(-1); const solve = idx => { if (idx >= s.length) return true; if (dp[idx] != -1) return dp[idx]; else { for (let i = 1; i
16:25 bhaia we search for the complete string s na but you mention after getting after getting "code" for searching "mik" that if condition will satisfy. but I think it will not run.
Once we have already confirmed that "code" is there in wordDict, Now we will search for remaining part of the string "mik" and hence we call recursion with the index starting at 'm' of mik
Not working for python. Strange sort of parameters being passed to recursive solve method. Why are we checking the whole "s" string in set(), second recursivve base case. If we are passing a slice of s to the second recursive base case then where is that happening.
this was my inital approatch it gives tle even after memozed (the reason being temp is always unique) class Solution { public: unordered_mapdp; bool solve(string& s,vector&wordDict,string temp){ if(temp == s){ return 1; } if(dp.find(temp)!= dp.end()){ return dp[temp]; } bool take = 0; for(int i = 0;i
what is the use of writing st.find(s) after the base case every time we are passing same string s in the recursion so we can write this condition starting of the string am i right sir
Problem extra character. Class solution { Public int min Extra char(string s,string [] dictionary){ setset=new Hash sat(); for(string word: dictionary) set.add(word); int[]dp= new int[s.length()]; Array. fill(dp,interger.MAX-VALUE); return split(s,0,dp,set); Private int split(string s.int index, int []dp,setdictionary){ if(index >=s.length()) return 0; if(dictionary. contains (s.substring (index))); return 0; if(dp(index)!=interger. MAX-VALUE) return dp(index); int min=s.length ()-index; for(int i=index +1; i
Okay bro thanks, i am preparing for placement from your playlist, i think many more are there who are referring your playlist. If you can finish it early, it would be great help to us
My solution was: ``` class Solution { public boolean wordBreak(String s, List wordDict) { Set wordSet = new HashSet(wordDict); int n = s.length(); int i = 0; while(i < n){ int j = i + 1; while(j
You have to break s in such a way that every broken part of s is present in wordDict. It’s not mandatory that every word in wordDict should be in s. Here s = “bb” Which can be broken into ‘b’ and ‘b’ which is present in wordDict
if(st.find(s) != st.end()) return true this statement is necessary or not like you are calling the whole string every time not the substring part so this statement check for the whole string every time not any substring as you explained in video that at the end if mik is present then it directly return true??
Hi , sorry to miss this. Since we will visit each n states only once (size of dp) And we also find substr which takes O(n) The T.C. Reduced to O(n^2) I will try to cover both TCs in videos
Bhai vapas nhi ana na string par poora word milna chayiye tabhi true hai ans. All possibilities hi try kr rahe hai hum recursion mei tree banake dekho ek bar Backtracking tab ata jab hume characters delete krne hote ya additional charatcter dale hote aur bola hota ki kya iska koi substring ans mei hai ya nahi ya related aisa kuch.
Ok, I was able to find the correct solution: Recursive: class Solution: def solve(self, idx, s, wordDict): if idx == len(s): return True if s in wordDict: return True
for l in range(1, len(s)+1): temp = s[idx: idx+l] if temp in wordDict and self.solve(idx+l, s, wordDict): return True
return False def wordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s) wordDict = set(wordDict) if s in wordDict: return True return self.solve(0, s, wordDict) Memoized: class Solution: def solve(self, idx, s, wordDict, dp): if idx == len(s): return True
if dp[idx] != -1: return dp[idx] if s in wordDict: return True
for l in range(1, len(s)+1): temp = s[idx: idx+l] if temp in wordDict and self.solve(idx+l, s, wordDict, dp): dp[idx] = True return dp[idx]
dp[idx] = False return dp[idx] def wordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s) wordDict = set(wordDict) if s in wordDict: return True dp = [-1 for _ in range(301)] return self.solve(0, s, wordDict, dp)
I was doing this but by using temp string and i m getting wrong ans.Can you explain why i am getting this? bool solve(int index,string s,vector& d,unordered_map&mp) { if(index>=s.size()) return true; string temp=""; for(int i=index;i
@@codestorywithMIK bhaiya we don't need to write the code for checking if string s is present in the set because we are not modifying it instead we can just check it once before calling the recursive function in the main function.
yes yes, I have added in the caption of the video at 16:26 of the video Please click on the Github link for the code , you can see there also. I also realised this. Thank you for pointing 😇❤️❤️❤️
I love the way you explain every concept from scratch.
Thank you so much for bringing such amazing content.❤
Thank you so much for trusting my small channel and it’s contents. 😇🙏
Bro please never stop this. I usually don't comment but this channel surely is underrated... Thanks for providing these conceptual understanding
Thank you so much 😇🙏
Sure, I will keep this moving
bro the thing i like most about your channel is that you tell the question from scratch so that viewer doesnt have to go and watch other related videos keep going and make videos this is your greatest strength that one can learn everything about a question from your channel without any need to watch full playlist
u guys are making coding worth it .this is the real humanity purpose of god.Thank u so much.
It means a lot.
Thank you so much 😇
this is hands down the best channel in terms of explaining everything in a simple way. please dont ever stop bro. u r doing a great job.
I don't know char 'd' of dynamic programming but the way you explain is really appreciable.
One of the best channels for a noob to intermediate to understand the concepts.
When you say trust me it isn't a medium proble
I trust you!!
Thank You :)
You made my day.
Thank you so much 🙏
One of the best explanation on RUclips. Thankyou so much Sir🙏🏻🙏🏻
Thank you so much ❤️😇🙏
Very helpful explaination of this question with detailed dry run and pseudocode. I had watched your videos for other Qs too. They are really very helpful. Thank you very much sir.👍
Small Correction. Substr also takes O(n) in worst case.
T.C : O(n * 2^n)
JAVA CODE :
class Solution {
private Boolean[] t;
int n;
public boolean wordBreak(String s, List wordDict) {
n = s.length();
t = new Boolean[s.length()];
return solve(s, 0, wordDict);
}
private boolean solve(String s, int idx, List wordDict) {
if (idx == n) {
return true;
}
if (t[idx] != null) {
return t[idx];
}
for (int endIdx = idx + 1; endIdx
sir thanks for providing java code. sir i request you to provide the java solution for every lecture from now.
When i will join a product base company . this channel will be one of the key preparation resources mentioned ❤
I am sure you will definitely get your dream job.
And thank you so much for your kind words ❤️❤️🙏🙏
for me this was new question but you made me understand me very nicely......First we just have to think about the recursion then memoization is very easy
Thank you so much 😇
doing a great job !!! CLEANEST EXPLANATION EVER
Hey Shashank,
Thank you so much for your kind words 😇🙏❤️
I was struggling in this question for some long.. but now by just watching your explanation I solved it myself....... Thankyou soo much for your wonderful explanation❣
Thank you 😇🙏
I really appreciate each and every thing about you brother....the way you explain every thing from scratch is just awesome. No one really explains that much. Loved your explanation.♥
Hi Rahul,
This really means a lot to me. Thank you for your kind words ❤️❤️🙏🙏
I am getting obsessed(saying positively) to solve POTD just because of you MIK🎉
Thank you so much Sachin ❤️
BRO THANKS TO YOU SINCE YOU ARE THE ONLY PERSON ON THE INTERNET WHO COULD EXPLAIN THIS QUESTION :- ALL POSSIBLE FULL BINARY TREES. NOW I WAS ABLE TO SOLVE TODAYS QUESTION ON MY OWN
ALSO PLEASE ADD ALL RELATED QUESTIONS OF THIS TYPE IF POSSIBLE
Hi Dhairya,
You made my day .
My video is being uploaded and I mentioned there that try the similar problem and you already did that.
I am so proud and happy.
Thanks a lot for sharing 😇🙏
@@codestorywithMIK another thing bhiya what if it says all possible trees. Then how do we deal with that since we dont care about all elements less than n in that case
In that case, we will choose every possible node as the left and right subtree.
For every i,
We can make the left subtrees from (start , i-1) as well as (i+1, end)
And similar for right subtrees
@@codestorywithMIK got it
Most Deserving and Underrated Channel
Means a lot ❤️😇🙏
Solved today's GFG POTD after watching this video, thank you so much bhaiya ❤❤
Hats Off to you, no one has explained like this. Such a crisp and clear explanation, which is indeed a need for interview preparation. Keep doing this good work🔥✨🙌
Always had doubts about this question, but now everything seems clear. Thank you bhaiya
So glad go hear that.
Thank you so much 😇🙏
Thank you so much for a clear tree diagram. It really does make things easy
in the for loop it should be l
substring concept very helpful , thanks a ton
Thank you 😇🙏
Guru ji pranam🙏🏻 I'm soo grateful i found your channel everybody tells the approach and the logic behind the questions but the way you taught using a proper structure or blueprint of how to structure your code is commendable thank you soo much......bhagwap aapko tarraki de🎉
Thank you so much 😊 🙏
Tabulation code.
Class solution {
Public boolean word Break(string s,listword Dict){
Setdict= new Hash Set(word Dict);
int n=s length ();
boolean []dp = new boolean (n+1);
dp(0)=true;
for(int i=1;i
Thanks a lot for sharing ❤️🙏
Thank you so much I understood the whole question since you explained it so easily☺❤❤
Thank you 😇🙏
Thanks for making this video. Where can i find the tabulation video for the same? not showing up on search.
Near to 7k 👏😊😊😊 give your best definitely you will reach the goal..
Thank you 😇🙏
Thank you for the wonderful explanation. One suggestion is please try to discuss the time and space complexity after optimization also.
Sure thing ❤️😇🙏
Don't loose hope Bro one day you definitely reach at height. you explain everything like no one can ❣❣
Thank you so much 😀
Thank you so much for the explaination, you made it very easy to understand🙏🙏 One question, are we considering the time complexity for searching the word in the unordered set? Also, could we have used map instead?
Itna achha koi kaise padha sakta hai
Unbelievable explanation . Love you 3000
Thank you 😇❤️
Best Explaination 💝
Thanks a lot 😊
sundar explanation once again ❤ abhi main graph bhi kar raha hoon aapke playlist se
Thank you 😇❤️
true bro striver ke baad sbse shi expalnation aapka lga bro please continue posting videos it help alot way i like is you also explained minor things that other youtuber dont do they just try to finish the video in small length
but you also explaoned the doubt portion of student that why that memset is there, why for loop is there in recurssion and many more
So glad to know that it’s helping you.
Will be posting more valuable contents.
Thank you 🙏❤️😇
re sir boht boht jaldi jaldi video arha hai ....kya baat hai ..waise hamare liye accha hi hai
Actually i try to complete before my office. Because after office I get really occupied in gym, swimming, sports etc.
so it’s better for me to upload early 😊
Thank you again for watching my channel 😇
@@codestorywithMIK how do you manage ? 🤯
@@codestorywithMIK Where do you work?
@@codestorywithMIK ok great
@@codestorywithMIK Bhai hume bhi motivation dedo tina kuch karne ka 🥺
Thanks a lot for such a clear explanation sir. I just had one doubt that why are we using unordered_set here what will happen if we check by using for loop?
It might give time limit exceeded error .
unordered_set provides O(1) time operation
@@codestorywithMIK alright sir got it. Thanks a lot😄🙌
Hello Sir! Was waiting for your video :) Thankyou
Most welcome! Hope it helps ❤❤❤
One thing left to be explained,why should we memoise it? From the initial inspection, it looks like there are no common subproblems. Then how come memoise help? I am sure there is an explanation for it but missed in the video.
However I liked the video overall. Mostly nobody goes through the process of thinking upfront before solving the problem. So that gives an illusion that the problem might be simple. You took it slow and explained all the gotchas very well. Thank you very much for this video.
let say text=aaaab
and we have dict= a, aa, aaa, aaaa.
now we divide text one by one
see
a, yes it is present in dict so we have divide, a aaab
similarly after 4 call we have divided, a a a a b
but b is not present in dict so, return false
means one back step at, a a a ab
but ab also not present so return false
a a aab
aab, now tried to divide here a a aa b, aa is present so we call for '"b' it will return false because of dp
so now we tried to divide like this, a a aab, but aab is also not present so return false.
so going back
we tried to divide like this, a aa ab, aa is present so call for ab, but for ab dp has false from before, so return false;
so going back
we tried to divide like this, a aaa b, aaa is present so call for b, but for b dp has false so return false
so going back
we tried to divide like this, aaaa b, aaaa is present so call for b, same story,
so going back
we tried to divide like this aaaab, but it is not present so return false
now finally we return false as loop over.
You make every problem easy to understand. Thanks for the simple explanation. But I couldn't understand memoization in your video, like why indices are memoized. So I stored strings and if they are broken down to dictionary words.
My Java code below(memoized in a little different way):
class Solution {
Map dp;
public boolean wordBreak(String s, List wordDict) {
dp = new HashMap();
Set dict = new HashSet(wordDict);
return solve(s, dict);
}
public boolean solve(String s, Set dict) {
if(dp.containsKey(s)) return dp.get(s);
if(dict.contains(s)) return true;
for(int i=1;i
Thank you so much Ravi.
Actually in recursion, most we memoize the parameters which are changing in every recursive call.
If you notice, idx was the only thing which was changing and hence I memoized idx.
@@codestorywithMIK yes I understood that but I couldn't make sense memoizing idx. Like in the tree diagram we see repetitive problems being memoized, so just want to understand from that perspective.
I got your point .
Actually I thought it in this way,
For a given idx, we will be looking at the substring s[idx, n] for different length 1,2,..n etc and if already it has been solved in some other path, we return.
@@codestorywithMIK Awesome!! Understood.
Shouldn't we pass the modified string i.e the second part of the string in the solve function inside for loop ??
Or shouldn't we check the string from idx to end in the base case ??
Like this =>
bool solve(int idx,string &s,int n){
if(idx>=n){
return true;
}
//Here in this part, we need to check the string from idx to end right ?? Else what is the use of passing and checking the same string in each recursive call ?
string temp = s.substr( idx , n - idx );
if( st.find(temp) != st.end() ){
return true;
}
for(int l=1;l
Hi Anshuman,
I got your point. Thanks for pointing this out. I have added that in the caption at 16:26
Thanks a lot
Thanks SIr🙏
Most welcome 😇
thanks man, amazing explanation
at 23:58, it is necessary to check the greater than condition because you are not putting a check on whether idx+l goes out of bound or not in the recursive call. Btw, badhiya explanation, mza agya
Correct
Thanks a lot 😇❤️
thank you so much.
Please make a video for 2-key keyboard and its similar questions.
Sure noted 😇
Thank you 😇
Thanks soo.much bro ❤ you super explanation 👍 👌 👏, .
Thank you 😇❤️
Thanks brother for making a tutorial on word break. ❤❤❤❤
You should launch a DSA course your explanation is superb.
May I know where product based company you work for.
Hi there.
Thank you for your kind words.
You can find everything about me here - github.com/MAZHARMIK ❤️😇🙏
Hi bro....recursion code time complexity would be 2^n or 2^n * n ?
Yes yes, corrected. See my pinned comment. Allso added caption on that part during the video.
Thank you so much for pointing this out ❣
As always Great Video 😍
Thank you so much 😀
Thanks for this nice explanation :)
Thank you 😇🙏
the code is wrong in the second base case you should have written
if(st.find(s.substr( idx , n - idx )) != st.end()) {
return true;
}
instead of
if(st.find(s)!=st.end()){
return true;
}
U made it so simple ❤
Thank you 😇❤️
Bhai ye apne for loop bata diya lekin mujhe yaad hai 2nd year mein tha 2022 mein 4 din mujhe lag gaye for loop kese work karta , kyuki koi video nhi thi uss time youtube pe
You nailed it dude!
Thank you Ayush 😇🙏
Hi,
Since in the recent videos you have been solving same prob using DP in diff vid. Can you please add the link for same problem using DP in the comments please. Many thanks, and as usual love your vids
Sure thing ❤️
Just adding 1 point. Here it's not a concept of taking one time, and not taking the other time, Here we have to take it, if it doesn't work, then keep it, and go on taking the next ones along with the previous ones until we found a matching pair.
I solved this question by myself same logic as palindrome partitioning❤
class Solution {
int [] dp;
boolean solve(String s, int idx, Set set) {
if (idx == s.length()) return true;
if (dp[idx]!=-1) return dp[idx]==1;
for (int i = idx; i < s.length(); i++) {
if (set.contains(s.substring(idx, i + 1)) && solve(s, i + 1, set)) {
dp[idx]=1;
return true;
}
}
dp[idx]=0;
return false;
}
public boolean wordBreak(String s, List wordDict) {
dp = new int[s.length()];
Arrays.fill(dp,-1);
Set set = new HashSet(wordDict);
return solve(s, 0, set);
}
}
Bhai you should start teaching at scalar or crio. You have very good teaching skills also + you are working at a good product based also. So you can guide students in the right direction + extra monetary benefits. Just a suggestion :D
Hi Tanuj,
Actually I have been getting offers from many paid platforms (I cant take name here), but there are few things which stop me from going ahead :
1) They want me to make videos by their names. i.e. no more codestorywithMIK
2) They want me to upload videos based on their plan. BUT, i always post videos based on my Subscribers’ needs.
3) They want me to advertise their platform in my videos. I personally don’t prefer promoting paid platforms (who charge big fees)
4) They will charge huge fees for courses that I will make as per their plan. I can’t charge Blindly huge fees.
This is the reason I never promote any paid platform in my videos even after getting offer from them.
Please share your points and suggestions also. I would love to hear 🙏❤️
@@codestorywithMIK Bro I do agree with you. I mean it takes balls to be take such decisions and avoid offers of such already established names. Actually worst part is all the good creators know that theses platforms are useless, creators like you and many others who are having maybe 500k+ subs learnt DSA on their own (mostly) and using free resources. There is guy ***ver who has all my respect as he is an amazing DSA teacher plus for the things he achieved but then in the videos he promotes useless online platforms which is not good tbh as it is misguiding for under confident students as they would do anything if placements are near, ending up wasting their money and time even though they can learn from channels like yours for free. But from a youtuber's pov, it is not wrong to do such promotions. Actually, you earned it through your hardwork that companies are offering you things. At the end of the day, its your money. 10 years down the line, no one would remember if they studied for free from codestorywithMIK or physics wallah or anywhere else, all they would remember is that they worked hard to gain it. So its totally your call.
if someone having diffculty understanding how memorization save time here,
see this
let say text=aaaab
and we have dict= a, aa, aaa, aaaa.
now we divide text one by one
see
a, yes it is present in dict so we have divide, a aaab
similarly after 4 call we have divided, a a a a b
but b is not present in dict so, return false
means one back step at, a a a ab
but ab also not present so return false
a a aab
aab, now tried to divide here a a aa b, aa is present so we call for '"b' it will return false because of dp
so now we tried to divide like this, a a aab, but aab is also not present so return false.
so going back
we tried to divide like this, a aa ab, aa is present so call for ab, but for ab dp has false from before, so return false;
so going back
we tried to divide like this, a aaa b, aaa is present so call for b, but for b dp has false so return false
so going back
we tried to divide like this, aaaa b, aaaa is present so call for b, same story,
so going back
we tried to divide like this aaaab, but it is not present so return false
now finally we return false as loop over.
You are the best ❤❤❤
Thank u sir for giving java code💫
Thank you for watching 😇🙏
Please please please please try to make a video of gfg problem.Waiting sir🙌🙌🙌
Sure. soon
sir please provide some good tips for placement as placement season is coming and provide some good resource for cs fundamentals
Once i get my degree and crack my dream company. after that i just wanna meet you to thank > Mik my fav
Thank you Nikhil 😇🙏
I am sure you will crack your dream company. Keep working hard ❤️❤️😇😇
Mannni Love your videos
Loved it!
Thank you ☺
Hi , Can u pls do a video on Leetcode 1705
Maximum Number of Eaten Apples , Difficult to understand
Not sure why but the CC subtitles are not showing...Anyway the content is soooo great!
Thank you for watching my video 😇🙏.
Actually the subtitles in English will be added soon 😇
Backtracking : TLE
class Solution:
def helper(self,index,s,words,l):
if index==len(s):
print(l.copy())
return True
flag=False
for length in range(1,len(s)+1):
substring=s[index:index+length]
if substring in words:
flag=flag or self.helper(index+length,s,words,l+[substring])
return flag
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
l=[]
return self.helper(0,s,set(wordDict),l)
My observation while partitioning we can just partition with the minimum length element in the words dictionary
Example:
s=codestorywithmik
words=["code","story","with","mik"]
we dont need to partition for all the length from 1 to len(s)
we can just take smallest word in words which is "mik" so conclude the length from
3 to len(s)
This is a small optimization for backtracking Hope this helps :)
class Solution:
def helper(self,index,s,words,l,mini):
if index==len(s):
print(l.copy())
return True
flag=False
for length in range(mini,len(s)+1):
substring=s[index:index+length]
if substring in words:
flag=flag or self.helper(index+length,s,words,l+[substring],mini)
return flag
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
l=[]
mini=min([len(i) for i in wordDict])
return self.helper(0,s,set(wordDict),l,mini)
Thanks a lot.
Indeed this comes under backtracking too.
However memoizing makes it fall under dp
thank sir .i have also solve from tries data structure
The question is very well explained but i have only one doubt the line no 11 is of no use then why would you write it correct me if i am wrong please
Sir apne jo st.find(s)!=st.end() lagai hai uska kya fayda hai......kyu sir s ki value to same hi rehri hai .....kya s.substr se s ki length choti hori hai.......koi btao plz
sir but time and space complexity is high, please share more optimize approach also
Yes,
Bottom up approach will come in DP Concepts Playlist
thanks for the explanation. i was able to figure out this one easily. here is my soln:
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
const set = new Set(wordDict);
const dp = Array(301).fill(-1);
const solve = idx => {
if (idx >= s.length) return true;
if (dp[idx] != -1) return dp[idx];
else {
for (let i = 1; i
Awesome 💪💪
Thank you sir, loving the content and you make it so easy for interview preparation. Really grateful that I found this channel. Reply krdo sirji
Thank you so much 😇❤️
16:25 bhaia we search for the complete string s na but you mention after getting after getting "code" for searching "mik" that if condition will satisfy. but I think it will not run.
Once we have already confirmed that "code" is there in wordDict,
Now we will search for remaining part of the string "mik" and hence we call recursion with the index starting at 'm' of mik
@@codestorywithMIK bhaia for search "mik" you told that if(st.find(s)) condition will run thats why i am telling.
@@sahebsarkar8330 I got your point.
Thanks for pointing this out. I have added that in the caption at 16:26
Thanks a lot
Not working for python. Strange sort of parameters being passed to recursive solve method. Why are we checking the whole "s" string in set(), second recursivve base case.
If we are passing a slice of s to the second recursive base case then where is that happening.
this was my inital approatch it gives tle even after memozed (the reason being temp is always unique)
class Solution {
public:
unordered_mapdp;
bool solve(string& s,vector&wordDict,string temp){
if(temp == s){
return 1;
}
if(dp.find(temp)!= dp.end()){
return dp[temp];
}
bool take = 0;
for(int i = 0;i
bro why not sliding window plz explain
1:09 videos to bahot logo k hain. Koi aapki tarah nahi parhata ❤. Thanks again for explaining from scratch and covering minute details.
what is the use of writing st.find(s) after the base case every time we are passing same string s in the recursion so we can write this condition starting of the string am i right sir
My bad, i will correct this part.
Let me add caption at that part
Thanks for pointing this out. I have added that in the caption at 16:26
Thanks a lot
thanks
in line 11 checking the complete string doesn't make any sence ...we have to check the substring in set
Word Break: Leetcode 139
class Solution {
public:
bool solve(int idx,string s, vector& wordDict){
if(s.size()==0)
return true;
if(idx >= wordDict.size() && s.size()>0)
return false;
auto found = s.find(wordDict[idx]);
string copy =s;
bool rem=false,rep =false,notRem=false;
if(found != string::npos){
copy = s;
s.erase(found,found + wordDict[idx].size());
rem |= solve(idx+1,s,wordDict);
rem |= solve(idx,s,wordDict);
cout
Problem extra character.
Class solution {
Public int min Extra char(string s,string [] dictionary){
setset=new Hash sat();
for(string word: dictionary)
set.add(word);
int[]dp= new int[s.length()];
Array. fill(dp,interger.MAX-VALUE);
return split(s,0,dp,set);
Private int split(string s.int index, int []dp,setdictionary){
if(index >=s.length()) return 0;
if(dictionary. contains (s.substring (index)));
return 0;
if(dp(index)!=interger. MAX-VALUE)
return dp(index);
int min=s.length ()-index;
for(int i=index +1; i
Hey bro, your graph conecpt playlist is completed?
2-3 topics are left only.
Will complete soon this month
Then will solve qns only
Okay bro thanks, i am preparing for placement from your playlist, i think many more are there who are referring your playlist. If you can finish it early, it would be great help to us
My solution was:
```
class Solution {
public boolean wordBreak(String s, List wordDict) {
Set wordSet = new HashSet(wordDict);
int n = s.length();
int i = 0;
while(i < n){
int j = i + 1;
while(j
You have to break s in such a way that every broken part of s is present in wordDict.
It’s not mandatory that every word in wordDict should be in s.
Here s = “bb”
Which can be broken into ‘b’ and ‘b’ which is present in wordDict
@@codestorywithMIK Thanks, now I get it. I got the question conversely
line 17 and 18 is necessary like you are passing whole string every time not the substring so i think it is not necessary right?
Hi there,
Sorry I didn’t get your qn.
Can you please elaborate ?
if(st.find(s) != st.end()) return true
this statement is necessary or not like you are calling the whole string every time not the substring part so this statement check for the whole string every time not any substring
as you explained in video that at the end if mik is present then it directly return true??
what will be the TC for MEMOIZATION
Hi , sorry to miss this.
Since we will visit each n states only once (size of dp)
And we also find substr which takes O(n)
The T.C. Reduced to O(n^2)
I will try to cover both TCs in videos
1:10 but you are the best
Thanks +3 ; // 4th day
Thank you ☺
I have solved it the other way around instead of looping from 1 to string length I looped over the wordDict.
Here's the code.
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
const cache = new Map();
function dfs(index) {
if(cache.has(index)) return cache.get(index);
if(index === s.length) {
return true;
}
for(let i = 0; i < wordDict.length; i++) {
const currentWord = s.substring(index, wordDict[i].length + index);
if(wordDict[i] === currentWord) {
const result = dfs(index + currentWord.length);
if(result) {
cache.set(index, true);
return true;
// return cache[index] = true;
// return true;
}
};
}
cache.set(index, false);
return false;
// return cache[index] = false;
// return false;
}
return dfs(0);
};
But it's a valid solution.
Aaj ki date vali video kab aayegi?
In an hour 😇
Sorry for delay, i usually travel during weekends
bhya isko backtracking se nhi kr skte kya??
Bhai vapas nhi ana na string par poora word milna chayiye tabhi true hai ans.
All possibilities hi try kr rahe hai hum recursion mei tree banake dekho ek bar
Backtracking tab ata jab hume characters delete krne hote ya additional charatcter dale hote aur bola hota ki kya iska koi substring ans mei hai ya nahi ya related aisa kuch.
I think in interview they will not allow to declare anything at global level
Indeed.
Always try to pass the variable in functions instead.
Can someone help here, not able to understand what is wrong :
class Solution:
def solve(self, idx, n, s, st):
if idx == n:
return True
if s in st:
return True
for l in range(1,n+1):
temp = s[idx:l]
print(temp)
if temp in st and self.solve(idx+l, n, s, st):
return True
return False
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
st = set(wordDict)
return self.solve(0, n, s, st)
Ok, I was able to find the correct solution:
Recursive:
class Solution:
def solve(self, idx, s, wordDict):
if idx == len(s):
return True
if s in wordDict:
return True
for l in range(1, len(s)+1):
temp = s[idx: idx+l]
if temp in wordDict and self.solve(idx+l, s, wordDict):
return True
return False
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
wordDict = set(wordDict)
if s in wordDict:
return True
return self.solve(0, s, wordDict)
Memoized:
class Solution:
def solve(self, idx, s, wordDict, dp):
if idx == len(s):
return True
if dp[idx] != -1:
return dp[idx]
if s in wordDict:
return True
for l in range(1, len(s)+1):
temp = s[idx: idx+l]
if temp in wordDict and self.solve(idx+l, s, wordDict, dp):
dp[idx] = True
return dp[idx]
dp[idx] = False
return dp[idx]
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
wordDict = set(wordDict)
if s in wordDict:
return True
dp = [-1 for _ in range(301)]
return self.solve(0, s, wordDict, dp)
I was doing this but by using temp string and i m getting wrong ans.Can you explain why i am getting this? bool solve(int index,string s,vector& d,unordered_map&mp)
{
if(index>=s.size()) return true;
string temp="";
for(int i=index;i
As always ❤
Thank you ☺
@@codestorywithMIK bhaiya we don't need to write the code for checking if string s is present in the set because we are not modifying it instead we can just check it once before calling the recursive function in the main function.
means the code line 17-18 can be removed to the main function
yes yes,
I have added in the caption of the video at 16:26 of the video
Please click on the Github link for the code , you can see there also.
I also realised this.
Thank you for pointing 😇❤️❤️❤️
Oh right, I didn't see 😅.
Tries data structure --> Leetcode
class Solution {
public:
class Trie{
public:
Trie *child[26];
bool isend = false;
};
void insert(string &word, Trie* root){
Trie *temp = root;
for(auto &ch : word){
if(!temp->child[ch-'a'])
temp->child[ch-'a'] = new Trie();
temp=temp->child[ch-'a'];
}
temp->isend = true;
}
bool search(string &word, Trie* root){
Trie *temp = root;
for(auto &ch : word){
if(!temp->child[ch-'a'])
return false;
temp=temp->child[ch-'a'];
}
return temp->isend;
}
int dp[305];
bool solve(string &s, Trie *root, int n, int start){
if(start==n) return true;
if(dp[start]!=-1)
return dp[start];
string str = "";
for(int i=start; i