Word Break Problem using Backtracking | Word Break Solution in JAVA

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we explain the Word Break problem using recursion and backtracking in Java. In this problem,

1. You are given n space separated strings, which represents a dictionary of words.
2. You are given another string which represents a sentence.
3. You have to print all possible sentences from the string, such that words of the sentence are present in dictionary.

.....................................................................................................................................................................

Pepcoding has taken the initiative to provide counselling and learning resources to all curious, skilful and dedicated Indian coders. This video is part of the series to impart industry-level web development and programming skills in the community.

We also provide professional courses with live classes and placement opportunities.
DSA Level 1 and Level 2

Webinar on GATE Preparation

We are also available on the following social media platforms: -

HAPPY PROGRAMMING!
Pep it up.....
#recursion #backtracking #wordbreak

[ankitbatra]

Nice solution sir! I would like to add one point here: the answer strings will always have an extra space character at the end, so if we want to avoid that, we will need to pop back the character from string before printing our answer.

[jaivishwakarma]

when u r cpp coder but still watches his video because of quality explanation

[deeptarkoroy]

Thanks sir.I did this ques without watching the video, its all because of u.

[harmanjeetsingh]

Your are my fav teacher sir!! i dont like to watch others video anymore

[jatinkumar]

Very nice explanation sir. I have a doubt. It is normal recursion right? Then why is it considered in backtracking? Also please explain its time and space complexity...

[vikkasmaheshwari]

Isme right string bnane ki bjaye hm index pass kr skte hai

[shrutiemu]

Sir your explanation is phenomenal and it gives clarity to the thinking process. But I faced certain time limit exceeded scenarios when the input is too huge .How can we handle such scenarios using recursion

[bibhusingh]

When was the Sumeet sir next Webinar.?
.
Because i really need to talk to him!
Please sir take a next Webinar as soon as possible.🙏

[pravinmudaliyar]

Sir, isme backtracking kaha ho rha h! Kahi pe bhi backtrack code nhi likha hua ? Btw ... Your teaching is just amazing. Thankyou sir🙏

[arpanbanejee]

Sir, iska memoized version pls bata dijiye, sab jagah bottom up kie hua hian

[sharmamukul]

I don't think this approach works for all possible cases. It works for cases when a word is of form str.substring(0, i+1) but fails when words are present in the form str.substring(i, j), i.e when words are present between the sentence and not necessarily at the start of sentence. Example:

{"ou", "suyoypayul", "eim","otehzri"}


In the above case, the above-discussed algorithm will not return all words present in the sentence (that are present in the dictionary).

[nilufaislam]

Sir what is the time and space complexity? And can we use dp here to store the intermediate results and improve the time ?

[deepakjumani]

sir ek hi sentence m dictionary vaale array ke 1 hi word ko do baar use ke skte h kya?

[sandeeprajurs]

just wanted to know how to prepare for ds and algos interview. Is it like we need to solve questions on all topics and in interview we just need to find the question belongs to which pattern that we have already solved...based on that we need to come up with solution rite?

[Sajju_]

It is only recursion not backtracking right??

[ravikishores]

Will it work for string=abcd and dictionary={ab, abc, d}.. Solution is picking "ab" first, then it will only search for cd..

[ankitamehra]

sir how to prepare for online tests..do we need to do competitive for that. under time pressure approach nahi anti dimaag main in online assessment

[mayur_madhwani]

code khud hi likh liya
itna sahi samjhaya hai na sir
jo question is topic se related nahi hai vo bhi ban jaate hai just because you teach how to think

[abheetsingh]

the submission fails for this test case:


["aaaa", "aaa"]

[punitsharma]

sir how many question is left in backtracking?