Word Break | Dynamic Programming | Leetcode #139

This video explains the word break problem using 3 techniques: Backtracking, Memoization and Tabulation Dynamic Programming. This is from leetcode 139. I have started from the intuitive backtracking approach and went on to explain the code writting strategy using intuitive approach and the method to convert it to a backtracking approach.

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

======================================PLEASE DONATE=============================
==============================================================================

=======================================================================
USEFUL LINKS:

RELATED LINKS:

[floatingfortress]

Using a dp array, you could bring down the space complexity from O(n^2) down to O(n). Time complexity remains O(n^3).

[sainathsingineedi]

Nobody:
Tech dose: uploads at 3:30 AM😂

[karan-xmtj]

I understood something from others videos after seeing yours every thing seems to be confusing

[nikhilraosanas]

Whenever i search better solution i always use to check is there any video from @tech dose

[chitranshsaxena]

18:50 How is time complexity O(N^2) for the recursion after memoization? Can someone please tell.

[JSDev]

i watched almost all of your videos and they really improved my problem solving skills a lot, I don't fear graphs, tries and heaps anymore, Thank you for that.

[ismail]

I watched your entire DP Playlist. It really helped a lot. Thanks for creating such quality vedios. Hoping for more vedios like this.

[preetambal]

Although i have solved this problem earlier still i was excited to see this video.. that's the level of your teaching skills..you explain stuffs in a very precise and streamlined manner..Thanks for all your explanations.

[satyendrayadav]

Rather than using the substr function, we can push each character at a time into a segmented string initialized with an empty string. This will bring down the complexity to O(n^2)

[vishwaskhurana]

wow, loved the explanation and the way you arrived at the most optimal solution. Thanks for the videos, keep them coming :)

[tanmaymehrotra]

The DP solution is hard to understand in my opinion. Its much simpler than what it explained.

[anmolsharma]

i didn't get the memoization solution why you are doing i-pos+1 let say if pos is 3 the first substring will now from pos (i.e 3) to (i-pos+1 ==
3 - 3 +1 = 1 ) how can be substring end value is smaller than the starting value it will surely give error

[rohangaonkar]

Typo. First approach
s.substr(pos, i+1)

[neetankumar]

Thanks man, best explaination for this question on utube

[sakshiramsinghani]

Really nice explanation, it must have taken a lot of efforts and hardwork. Thanks a lot!!

[rohandevaki]

and why did you create the String t? if you are not using it? at 16:40

[divyagracie]

Brute force, better for loop variable:


class Solution {
private Set<String> dictSet = new HashSet<>();
public boolean wordBreak(String s, List<String> wordDict) {
for(String str : wordDict) {
dictSet.add(str);
}
return wordBreakRecur(s, 0);
}
private boolean wordBreakRecur(String s, int pos) {
if(pos == s.length()) return true; //whole string has passed.

//all substrings starting at 'pos', ending at all possible end and
//wordBreakRecur on s from next position of matched word.
for(int end = pos + 1; end <= s.length(); end ++) {
String split = s.substring(pos, end);
"+ split);
if(dictSet.contains(split)) {
if(wordBreakRecur(s, end)) {
return true;
}
}
}
return false;
}
}

[jinny]

Your explanation is always clear and easy to understand. I've learned a lot. :) But... could you please also do binary search problems? It's quite hard to figure out why I need to solve the problem with binary search. For example, Leetcode 774 Minimize Max Distance to Gas Station. I want to know about your thinking process when you encounter hard binary search problems! Anyways thank you always Techdose, I hope you gain more subscribers soon! You deserve more and more.

[pyarsingh]

so sir in the Backtracking approach also we are creating substring every time so should Not the Time complexity be O(2^N * N ) this multiple of N for creating substring every time?? As its is N^2 * N is Dp memoization approach

[TabmansTube]

I don't see how memo helps as the result stored in memo will only be used once (when evaluated) and never be re-used, say there is a valid sentence ilikemango, the call stack is like this

wb(i)
/ \
true wb (like)
/ \
true wb(mango)
/ \
true true

so where is the memo helping as a cache & preventing recomputation?