Word Break | Tree Diagram | Recursion | Memoization | Similar Problems | Leetcode-139

[@prernarawat4392]

I love the way you explain every concept from scratch. Thank you so much for bringing such amazing content.❤

[@codestorywithMIK]

Thank you so much for trusting my small channel and it’s contents. 😇🙏

[@GAMERBOY-vu6wt]

Bro please never stop this. I usually don't comment but this channel surely is underrated... Thanks for providing these conceptual understanding

[@codestorywithMIK]

Thank you so much 😇🙏 Sure, I will keep this moving

[@codestorywithMIK]

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

[@zealrodrigues8495]

sir thanks for providing java code. sir i request you to provide the java solution for every lecture from now.

[@VarunSharma-xd8xd]

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

[@level_up.1908]

u guys are making coding worth it .this is the real humanity purpose of god.Thank u so much.

[@codestorywithMIK]

It means a lot. Thank you so much 😇

[@pranavpranjal2717]

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.

[@greyhatbeast]

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 :)

[@codestorywithMIK]

You made my day. Thank you so much 🙏

[@dhairyachauhan6622]

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

[@dhairyachauhan6622]

ALSO PLEASE ADD ALL RELATED QUESTIONS OF THIS TYPE IF POSSIBLE

[@codestorywithMIK]

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 😇🙏

[@dhairyachauhan6622]

@@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

[@codestorywithMIK]

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

[@dhairyachauhan6622]

@@codestorywithMIK got it

[@anjaliupadhyay1915]

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❣

[@codestorywithMIK]

Thank you 😇🙏

[@jagratgupta8392]

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

[@codestorywithMIK]

Thank you so much 😇

[@rv5778]

When i will join a product base company . this channel will be one of the key preparation resources mentioned ❤

[@codestorywithMIK]

I am sure you will definitely get your dream job. And thank you so much for your kind words ❤️❤️🙏🙏

[@sachinmohanty4577]

I am getting obsessed(saying positively) to solve POTD just because of you MIK🎉

[@codestorywithMIK]

Thank you so much Sachin ❤️

[@harjaspreetsingh8416]

One of the best explanation on KZbin. Thankyou so much Sir🙏🏻🙏🏻

[@codestorywithMIK]

Thank you so much ❤️😇🙏

[@yeshitamotwani2701]

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.👍

[@asitkumar3164]

Most Deserving and Underrated Channel

[@codestorywithMIK]

Means a lot ❤️😇🙏

[@dayashankarlakhotia4943]

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

[@codestorywithMIK]

Thanks a lot for sharing ❤️🙏

[@gauravbanerjee2898]

Solved today's GFG POTD after watching this video, thank you so much bhaiya ❤❤

[@rahulmandal3018]

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.♥

[@codestorywithMIK]

Hi Rahul, This really means a lot to me. Thank you for your kind words ❤️❤️🙏🙏

[@shashanksp9168]

doing a great job !!! CLEANEST EXPLANATION EVER

[@codestorywithMIK]

Hey Shashank, Thank you so much for your kind words 😇🙏❤️

[@keertilata20]

Always had doubts about this question, but now everything seems clear. Thank you bhaiya

[@codestorywithMIK]

So glad go hear that. Thank you so much 😇🙏

[@nikiteshnandale8264]

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🔥✨🙌

[@ezcoding69]

re sir boht boht jaldi jaldi video arha hai ....kya baat hai ..waise hamare liye accha hi hai

[@codestorywithMIK]

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 😇

[@thekindspill]

@@codestorywithMIK how do you manage ? 🤯

[@sauravchandra10]

@@codestorywithMIK Where do you work?

[@ezcoding69]

@@codestorywithMIK ok great

[@souravjoshi2293]

@@codestorywithMIK Bhai hume bhi motivation dedo tina kuch karne ka 🥺

[@MounikaEMB]

Near to 7k 👏😊😊😊 give your best definitely you will reach the goal..

[@codestorywithMIK]

Thank you 😇🙏

[@ritwiksingh5311]

sundar explanation once again ❤ abhi main graph bhi kar raha hoon aapke playlist se

[@codestorywithMIK]

Thank you 😇❤️

[@robot3.077]

Itna achha koi kaise padha sakta hai

[@manish6801]

Don't loose hope Bro one day you definitely reach at height. you explain everything like no one can ❣❣

[@codestorywithMIK]

Thank you so much 😀

[@wearevacationuncoverers]

Thank you so much for a clear tree diagram. It really does make things easy

[@harshupadhyay2422]

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🎉

[@codestorywithMIK]

Thank you so much 😊 🙏

[@IconOfSeas]

substring concept very helpful , thanks a ton

[@codestorywithMIK]

Thank you 😇🙏

[@abby_bytes]

Hello Sir! Was waiting for your video :) Thankyou

[@codestorywithMIK]

Most welcome! Hope it helps ❤❤❤

[@niyatimarskole]

Thank you so much I understood the whole question since you explained it so easily☺❤❤

[@codestorywithMIK]

Thank you 😇🙏

[@MAYANKKUMAR-dh9eh]

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

[@codestorywithMIK]

So glad to know that it’s helping you. Will be posting more valuable contents. Thank you 🙏❤️😇

[@debanjansarkar3328]

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.

[@ravitejasriram4284]

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

[@codestorywithMIK]

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.

[@ravitejasriram4284]

@@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.

[@codestorywithMIK]

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.

[@ravitejasriram4284]

@@codestorywithMIK Awesome!! Understood.

[@beinghappy9223]

Unbelievable explanation . Love you 3000

[@codestorywithMIK]

Thank you 😇❤️

[@sauravchandra10]

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

[@codestorywithMIK]

Correct Thanks a lot 😇❤️

[@souravjoshi2293]

1:09 videos to bahot logo k hain. Koi aapki tarah nahi parhata ❤. Thanks again for explaining from scratch and covering minute details.

[@kartikforwork]

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.

[@shadab9764]

Best Explaination 💝

[@codestorywithMIK]

Thanks a lot 😊

[@thunderstormgaming4353]

Thank you for the wonderful explanation. One suggestion is please try to discuss the time and space complexity after optimization also.

[@codestorywithMIK]

Sure thing ❤️😇🙏

[@kishan.17]

Thanks soo.much bro ❤ you super explanation 👍 👌 👏, .

[@codestorywithMIK]

Thank you 😇❤️

[@ankur20010]

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.

[@kartikforwork]

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.

[@jagadeeshp1163]

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)

[@codestorywithMIK]

Thanks a lot. Indeed this comes under backtracking too. However memoizing makes it fall under dp

[@abhishekkumar-cf2ft]

I think there is no need of keeping extra check of if(st.find(s)) { return true; } because it is already being checked inside for loop . Btw great explanation 😅.

[@kartikrameshchavan4710]

Thanks SIr🙏

[@codestorywithMIK]

Most welcome 😇

[@tanujarora4906]

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

[@codestorywithMIK]

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 🙏❤️

[@divyanshmishra5121]

@@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.

[@shreyxnsh.14]

thanks man, amazing explanation

[@NikhilRaj-wv6nf]

Once i get my degree and crack my dream company. after that i just wanna meet you to thank > Mik my fav

[@codestorywithMIK]

Thank you Nikhil 😇🙏 I am sure you will crack your dream company. Keep working hard ❤️❤️😇😇

[@anuppatankar4294]

As always Great Video 😍

[@codestorywithMIK]

Thank you so much 😀

[@adnanhasan8958]

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; }

[@divyanshkhandelwal5191]

then how it is getting passed, anyways I also have changed it to this

[@tusharsingh1257]

in the for loop it should be l

[@aayushkumar4679]

thank you so much. Please make a video for 2-key keyboard and its similar questions.

[@codestorywithMIK]

Sure noted 😇 Thank you 😇

[@harshpatel1385]

I solved this question by myself same logic as palindrome partitioning❤

[@harshpatel1385]

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); } }

[@anshumantripathy115]

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

[@codestorywithMIK]

Hi Anshuman, I got your point. Thanks for pointing this out. I have added that in the caption at 16:26 Thanks a lot

[@AyushRaj-we2og]

You nailed it dude!

[@codestorywithMIK]

Thank you Ayush 😇🙏

[@divyam69]

Thanks for this nice explanation :)

[@codestorywithMIK]

Thank you 😇🙏

[@sushmitavats8547]

Thank u sir for giving java code💫

[@codestorywithMIK]

Thank you for watching 😇🙏

[@prathameshbhat9816]

Mannni Love your videos

[@honey6567]

thank sir .i have also solve from tries data structure

[@dhairyachauhan6622]

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

[@oqant0424]

U made it so simple ❤

[@codestorywithMIK]

Thank you 😇❤️

[@adarshdhital007]

Loved it!

[@codestorywithMIK]

Thank you ☺

[@justlc7]

Thanks for making this video. Where can i find the tabulation video for the same? not showing up on search.

[@amandixit8342]

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

[@ugcwithaddi]

You are the best ❤❤❤

[@arjunprasad1071]

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?

[@madhurjyadoley3100]

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.

[@codestorywithMIK]

Hi there. Thank you for your kind words. You can find everything about me here - github.com/MAZHARMIK ❤️😇🙏

[@floatingpoint7629]

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

[@codestorywithMIK]

Awesome 💪💪

[@shabananoor9423]

1:10 but you are the best

[@ankitgupta2745]

Please please please please try to make a video of gfg problem.Waiting sir🙌🙌🙌

[@codestorywithMIK]

Sure. soon

[@VedBrahmbhattBEE]

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?

[@codestorywithMIK]

It might give time limit exceeded error . unordered_set provides O(1) time operation

[@VedBrahmbhattBEE]

@@codestorywithMIK alright sir got it. Thanks a lot😄🙌

[@alisheheryar1770]

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.

[@tushu__22]

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

[@codestorywithMIK]

Thank you so much 😇❤️

[@invinishku1542]

Hi bro....recursion code time complexity would be 2^n or 2^n * n ?

[@codestorywithMIK]

Yes yes, corrected. See my pinned comment. Allso added caption on that part during the video. Thank you so much for pointing this out ❣

[@samridhshubham8109]

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

[@codestorywithMIK]

Sure thing ❤️

[@jayeshshinde9521]

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

[@abhinay.k]

thanks

[@dayashankarlakhotia4943]

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

[@abc-ym4zs]

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

[@codestorywithMIK]

My bad, i will correct this part. Let me add caption at that part

[@codestorywithMIK]

Thanks for pointing this out. I have added that in the caption at 16:26 Thanks a lot

[@tejaspatel2212]

Hey bro, your graph conecpt playlist is completed?

[@codestorywithMIK]

2-3 topics are left only. Will complete soon this month

[@codestorywithMIK]

Then will solve qns only

[@tejaspatel2212]

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

[@ahaddesirement4594]

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

[@codestorywithMIK]

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

[@ahaddesirement4594]

@@codestorywithMIK Thanks, now I get it. I got the question conversely

[@lazyhead1276]

sir please provide some good tips for placement as placement season is coming and provide some good resource for cs fundamentals

[@yuanliu5945]

Not sure why but the CC subtitles are not showing...Anyway the content is soooo great!

[@codestorywithMIK]

Thank you for watching my video 😇🙏. Actually the subtitles in English will be added soon 😇

[@iamnoob7593]

Hi , Can u pls do a video on Leetcode 1705 Maximum Number of Eaten Apples , Difficult to understand

[@satendra6200]

in line 11 checking the complete string doesn't make any sence ...we have to check the substring in set

[@bikram_m439]

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

[@mathematics7746]

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?

[@codestorywithMIK]

Hi there, Sorry I didn’t get your qn. Can you please elaborate ?

[@mathematics7746]

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??

[@aman3210]

Thanks +3 ; // 4th day

[@codestorywithMIK]

Thank you ☺

[@honey6567]

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

[@akshanshsharma6025]

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

[@sahebsarkar8330]

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.

[@codestorywithMIK]

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

[@sahebsarkar8330]

@@codestorywithMIK bhaia for search "mik" you told that if(st.find(s)) condition will run thats why i am telling.

[@codestorywithMIK]

@@sahebsarkar8330 I got your point. Thanks for pointing this out. I have added that in the caption at 16:26 Thanks a lot

[@abhishekverma7604]

bhya isko backtracking se nhi kr skte kya??

[@tanujarora4906]

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.

[@commonpeoplepodcast9718]

sir but time and space complexity is high, please share more optimize approach also

[@codestorywithMIK]

Yes, Bottom up approach will come in DP Concepts Playlist

[@Abyssal_Ink]

bro why not sliding window plz explain

[@Piyushraj0]

As always ❤

[@codestorywithMIK]

Thank you ☺

[@Piyushraj0]

@@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.

[@Piyushraj0]

means the code line 17-18 can be removed to the main function

[@codestorywithMIK]

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 😇❤️❤️❤️

[@Piyushraj0]

Oh right, I didn't see 😅.

[@oqant0424]

what will be the TC for MEMOIZATION

[@codestorywithMIK]

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

[@kunal4710]

HII MIK BHAIYA , I HAVE ONE DOUBT DECLARING GLOBAL VARIABLE (LIKE YOU HAVE DECLARED MAP) OR DECLARING MAP INSIDE MAIN FUNCTION AND THEN PASSING IT TO THE FUNCTION - WHICH IS CONSIDERED AS A GOOD PRACTISE , DOES IT AFFECT TIME COMPLEXITY CAN YOU PLEASE TELL THIS my code for your reference - bool f(int idx, string s,vector &dp , unordered_map mp){ if(idx>=s.length()){ return true; } if(dp[idx] !=-1){ return dp[idx]; } for(int i=idx;i

[@codestorywithMIK]

Always remember following points: 1. It's never a good idea to use global variables. Because when the code and logic becomes big and complex, then managing global variables becomes really tough and might also result in wrong results when by mistake global variable is changed somewhere. 2. Now, coming to your next Qn, when we pass a parameter in any function, compiler creates a copy of it every time that function is called. Creation of copy slows down the code. How to fix this ? You can pass your parameter by reference (use & before the param) For example : return f(0,s,dp,mp); f(int idx, string s,vector &dp , unordered_map &mp){ //// } This allows to not create a new copy of variables(parameters) being passed. But you need to be careful when you pass things by reference , if you change that parameter in the function, then that same change is reflected upon the called function in that variable. for example : int main() { int a = 2; func(a); cout

[@kunal4710]

@@codestorywithMIK FIRST OF ALL THANK YOU SO MUCH FOR SUCH DETAILED EXPLANATION IT DEFINATELY CLEAR MUCH THINGS BUT WHAT I WAS ASKING IS SHOULD WE PASS our map through function call or we should declare it as a global variable the way you declared in this question AS I HAVE READ MANY TIMES THAT WE SHOULD NOT USE GLOBAL DECLARATIONS MUCH public: unordered_map mp; .............. OR f(int idx, string s,vector &dp , unordered_map &mp){ //// } WHICH IS CONSIDERED A GOOD PRACTISE ?

[@codestorywithMIK]

Yes yes, Pass it to the function instead of global variables 😊

[@kunal4710]

@@codestorywithMIK Got it 🥳

[@ankitgupta2745]

Aaj ki date vali video kab aayegi?

[@codestorywithMIK]

In an hour 😇 Sorry for delay, i usually travel during weekends

[@aadil4236]

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.

[@codeandtalk6]

❤❤

[@codestorywithMIK]

Thank you for the support everyday 🙏😇