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

****************Similar Qns :

This is the 53rd Video on our Dynamic Programming (DP) Playlist.
In this video we will try to solve a very famous DP Problem - Word Break (Leetcode-139).

Trust me, this will no longer be a Medium Problem.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Word Break
Company Tags : Amazon, Google, IBM, MAQ Software, Microsoft, Walmart, Zoho

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[prernarawat]

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

[GAMERBOY-vuwt]

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

[rv]

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

[VarunSharma-xdxd]

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

[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<String> wordDict) {
n = s.length();
t = new Boolean[s.length()];
return solve(s, 0, wordDict);
}

private boolean solve(String s, int idx, List<String> wordDict) {
if (idx == n) {
return true;
}

if (t[idx] != null) {
return t[idx];
}

for (int endIdx = idx + 1; endIdx <= n; endIdx++) {

String split = s.substring(idx, endIdx);

if (wordDict.contains(split) && solve(s, endIdx, wordDict)) {
return t[idx] = true;
}
}

return t[idx] = false;
}
}

[level_up.]

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

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

[pranavpranjal]

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.

[nishant]

was able to come up with brute force.. Thanks for explanation

[gauravbanerjee]

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

[KangkanaBaruah-ld]

Java recursive code :
class Solution {
int n;
Set<String> st =new HashSet<>();
private boolean solve(String s, int idx){
if(idx>=n){
return true;
}
if(st.contains(s)){
return true;
}
for(int l=1;l<=n-idx;l++){
String temp=s.substring(idx, idx+l);
if(st.contains(temp) && solve(s, idx+l)){
return true;
}
}
return false;
}
public boolean wordBreak(String s, List<String> wordDict) {
n=s.length();
st = new HashSet<>(wordDict);
return solve(s, 0);
}
}

[jagratgupta]

for me this was new question but you made me understand me very we just have to think about the recursion then memoization is very easy

[saiakshagn]

Best explanation of recursion compared to other YouTubers!

[RahukndalMondal-xczw]

i really love your problem solving approach and explanation method. Thank you sir 🫡

[anjaliupadhyay]

I was struggling in this question for some long.. but now by just watching your explanation I solved it Thankyou soo much for your wonderful explanation❣

[dhairyachauhan]

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

[harjaspreetsingh]

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

[yeshitamotwani]

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

[shashanksp]

doing a great job !!! CLEANEST EXPLANATION EVER

[bheemibaiSabavath]

Yesterday i gave my interview and i got shortlisted for technical round 2 because of you(thanks mik) and interviewer asked me about this question and gave me 15 mins to solve this but i couldn't figured it out.
After that i got rejected, but i am not feeling low because i decided now to restart dp, graphs, trees, backtracking and all dsa concepts each day i will solve atleast 5 questions.
(Thanks MIK)