Word Break II | 2 Recursion Approaches | Backtracking | Memoization | Tree Diagram | Leetcode 140

This is the 15th Video of our Playlist "Backtracking : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a classic Backtracking Problem : Word Break II | 2 Recursion Approaches | Backtracking | Memoization | Tree Diagram | | Leetcode 140 | codestorywithMIK

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.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Word Break II | 2 Recursion Approaches | Backtracking | Memoization | Tree Diagram | | Leetcode 140 | codestorywithMIK
Company Tags : Meta Phone Screen Interview, Twitter, Snapchat, Dropbox, Uber, Google

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

Summary :
### Summary of Approaches

#### Approach 1: Simple Backtracking
- **Time Complexity:** \(O(2^n)\)
- **Space Complexity:** \(O(n)\) for recursion depth and \(O(2^n)\) for storing results.
- **Method:** Recursively explore all possible word breaks by trying each substring. If a substring is in the dictionary, continue with the rest of the string. Store valid sentences in the result list.

#### Approach 2: Backtracking with Memoization
- **Time Complexity:** \(O(2^n)\)
- **Space Complexity:** \(O(n)\) for recursion depth and \(O(2^n)\) for memoization and storing results.
- **Method:** Enhance backtracking by storing results of subproblems in a memoization map to avoid redundant calculations. Check the memoization map before solving subproblems to improve efficiency.

**Comparison:**
- Both approaches explore all possible ways to break the string into valid words.
- Approach 2 is more efficient due to memoization, which reduces redundant calculations and improves execution time for larger inputs.

✨ Timelines✨
00:00 - Introduction

#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 #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

[Kumar-uplj]

Bhai thanks I got selected as 6month intern at gameberry mne dsa 3 month phle hi chhod dia tha bs tumhari video dkh leta tha roj consistency k lie and I got selected thanks again brother

[AkemnoorSingh]

Kya explain kia h bhai....aapne english bolne pe focus ni kia, delivery pe kia h. 🔝
Fantastic.

[akshaychavan]

MIK, I solved this question in my very first attempt within 20 minutes!!
Sign of progress 🙂
Thanks to you 🙌

[saarthakkhandelwal]

Solved it by myself, but still watching to understand your approach. Love your Graph playlist especially

[KunalSingh-olzx]

I did it on my own I solved exactly at the moment you uploaded it. It was all thanks to your story and lessons from few days back.
Thanks so much! for helping me solve my first hard question in first try.
Thank you.

[kartik]

Came here to check out if I was thinking of the same approach as you. And I was right !
This question was not hard at all after watching your previous videos! ✨✨✨

[Innovision]

I solved it on my own it all because of your previous videos thank you bhaiya❤❤🌟🌟

[aws_handles]

I solved it on my own. You removed my fear of backtracking 😍😍😍

[wearevacationuncoverers]

I don't know if you remember, but I was the one who had asked when to use for loop and when not. Tree diagram helped me a lot to clear my doubt. thank you. love your explanations.

[EB-otuu]

I solved it in 20 minutes on my own. Thank you so much.
Came here to thank and support you

[gui-codes]

maine bhi khud se bana liya is qn ko 😭😭😭. thank you mik for improving my problem solving

[himanshusharma]

Sir, can u make a video on how a beginner go through your playlist because its really very helpful, roadmap if possible, on what to do next in your channel playlist after one playlist so that wiithin 6 months a person should be able to solve all questions in leetcode weekly and biweekly

[gauravbanerjee]

Thanks a lot bhaiya ❤❤ & Congrats for 49k subs 🥳🥳 1 more k to go 🎉

[souravjoshi]

Done in the morning already. thanks to you mik

[confuseduck]

it seems like a medium level question however it took me time to understand the tabulation part

[ankanbrahmachary]

this problem is exactly same as palindrome partition string ... just instead of checking palindrome check if word exists in dict

[parulagrawal]

Could you tell why the time complexity is 2^n ?

Wouldn't it be 2^(n-1) as there'll be these many leaves of the tree

[dayashankarlakhotia]

public List<String>wordBreak(String s, List<String>wordDict){
Set<String>wordSet=new HashSet<>(wordDict);
List<String>ans=new ArrayList<>();
backtrack(s, wordSet, new StringBuilder(), ans, 0);
return ans;
}
private static void backtrack(String s, Set<String>wordSet, StringBuilder sb, List<String>ans, int sIdx){
if(sIdx==s.length()){

return;
}
for(int
String word=s.substring(sIdx, endIdx);
if(wordSet.contains(word)){
int curLen=sb.length();
sb.append(word).append(" ");
backtrack(s, wordSet, sb, ans, endIdx);
sb.setLength(curLen);
}
}
}
}🎉❤

[Code_loading]

Brother please make a vedio on today's leetcode contest question...Find the number of good pairs 2 after contest overs

[IamAmitBarman]

can you share a video, how after all that iteration the ans is getting stored? i mean to say take and dont take ke end pe kaise result a raha hai..