Word Break 2 | Leetcode #140

This video explains the word break 2 problem from leetcode #140. It is a very important interview problem on string. There are multiple techniques to solve this using Dynamic Programming as well as TRIE, MAP, SET etc. I had already explained the Dynamic Programming approach in the previous video on Word Break 1 problem (LINK is given below). In this video, I have explained an alternative Recursion + TRIE approach for solving the problem efficiently. It is a 2 step process. First store word dictionary in the TRIE and then use Recursion to do all valid partition for words. When we end the string by making all valid partitions then simply store the built sentence in our answer array of string.
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:

[PegasusKr]

I found your channel a month ago and walkthrough almost all the uploaded videos. Thanks for new uploading!

[pradeepmehra]

Love your way of teaching. I was able to code the solution myself even after watching only 7mins of the video

[jnayehsirine]

i stumbled upon this channel, one of my best discoveries of the day !!!!

[serhattural]

Best explanation again. I think we can optimize Trie search because for each character we are starting search from root of Trie. if we keep last node, we can continue at current position on Trie. If we find a new word or reach leaf, we can reset to root for new search.

[VikasSharma-egmc]

You explained problem like you have done PhD in it.
Explained deeply and clearly with every possible concept

[coder]

Oh man you're back I can't believe my eyes 😁

[darshansimha]

Hey! I don't see any advantage of using a Trie, because at any point you will be iterating over all the words and most languages have an indexOf method to see if a word is a prefix of a string. So why do the Trie, the TC is anyway 2^N. We literally gained no improvement in the time by using Trie and not to mention we used additional space. I might be wrong. Here is my implementation in Java.

``` public List<String> wordBreak(String s, List<String> wordDict) {
List<String> result = new ArrayList<>();
wordBreakHelper(s, wordDict, result, new StringBuilder());
return result;
}

private void wordBreakHelper(String s, List<String> wordDict, List<String> result, StringBuilder current) {
if (s.equals("")) {
// We do this because we don't want to add space on the last word
- 1);

return;
}
for (String word : wordDict) {
if (s.indexOf(word) == 0) {
current.append(word);
current.append(" ");
wordBreakHelper(s.substring(word.length(), s.length()), wordDict, result, new StringBuilder(current));
// We do this because we want to remove the last added space and the last word
- word.length() - 1, current.length());
}
}
return;
}
```

[kanavguleria]

upper one seems little complex - this code worked for me when solved in gfg - class Solution{

public static boolean breakIt(int n, List<String> al, List<String> dict
, String s, String ans, int next)
{
// System.out.println(ans+" ---- "+next);
if(s.length() <= next )
{
//
ans = ans.substring(0, ans.length()-1);
al.add(new String(ans));
return true;
}

for(int i=next;i<n;i++)
{


String k1 = s.substring(next, i+1);

if(dict.contains(k1))
{
int temp = next;
next = i+1;
breakIt(n, al, dict, s, ans+k1+" ", next);

next = temp;

}

}


return false;


}

static List<String> wordBreak(int n, List<String> dict, String s)
{
String ans = "";

List<String> al = new ArrayList<>();
int t = s.length();
breakIt(t, al, dict, s, ans, 0);

return al;
}
}

[HimanshuKumar-slud]

Sir you are great teacher, your way to explain complex things in easy ways fantastic. sir please upload more and more problems solution of leetcode please sir.

[paragroy]

Nice explanation keep on making such content is really amazing

[ismail]

After Long time bro. Happy to see you again. Bro can you do some good playlist for system design.

[ravishasharma]

Hey! This is not related to this question. I got a question in a company's OA and I don't find a solution for it. Can you help? The question is: Given some points of the coordinate plane like (x, y), we need to find the minimum number of straight lines so that all these points get covered. Also, it's similar to LeetCode: 149. I have tried this a lot, can't solve it properly.

[martinharris]

after a looong time !!!! where were u?

[ayushgoel]

Hi bro, please make some tutorial for machine coding rounds and low level design, currently there is no content present on such topics

[palakmantry]

Why is the trie more efficient than map?