# The Word Break Problem

Objec­tive : Given an string and a dic­tio­nary of words, find out if the input string can be bro­ken into a space-separated sequence of one or more dic­tio­nary words.

Exam­ple:

```dictionary = ["I" , "have", "Jain", "Sumit", "am", "this", "dog"]

String = "IamSumit"

Output: "I am Sumit"

Output : String can't be broken
```

Approach: Back­track­ing– Naive Approach

• Nav­i­gate the given input string.
• Take a blank string and keep adding one char­ac­ter at a time to it.
• Keep check­ing if the word exist in the dictionary.
• If word exist in the dic­tio­nary then add that word to the answer string and make recur­sive call to the rest of the string.
• If any of the recur­sive call returns false then back­track and remove the word from the answer string and again keep adding the char­ac­ters to string.
• If all the recur­sive calls return true that means string has been bro­ken successfully.
• See the code for bet­ter explanation.

Com­plete Code:

If we notice here we are­solv­ing many sub-problems repeatedly.

Word Break Prob­lem — Over­lap­ping Subproblems

Dynamic Pro­gram­ming to Rescue:

• We will use top-down  approach.
• Before we solve it for any string check if we have already solve it.
• We can use another HashMap to store the result of already solved strings.
• When­ever any recur­sive call returns false, store that string in HashMap.
• See the code for bet­ter explanation

Com­plete Code:

```Output:
this is sumit jain
```

#### You may also like...

• Rahul Shukla

http://www.ideserve.co.in/learn/word-break-problem
Here is a nice expla­na­tion of the algorithm.

• CRH

Can you give an input exam­ple using which Line 10, 11 will be used in the DP approach

• John

Both recur­sion and DP appear to be overkill to me. You just scan through the string and just if a sub­string (i to the end) is in the dic­tio­nary. If not, just stop and return false. If a word is found, then keep scan­ning the rest. Actu­ally mem­o­iza­tion is use­less. It depends on the dic­tio­nary is a list or a hash table.

• biswa­jit singh

exactly when i read the prob­lem the same thing came to my mind. we just need to scan through the dic­tio­nary and check whether dictionary[i] is a sub­string in the word . and keep on doing this until the length matches. the there is no point going for recur­sion unless you want to waste your time.

• MURHY

This approach is just recur­sion way of solv­ing prob­lem. There is no back­track­ing here.

• tuto­ri­al­hori­zon

Back­track­ing is there. We are using HashMap to store the strings which we have already checked and if it is checked then do not call the recur­sive func­tion for that. Its a Top-Down DP approach.

• rai.kaushal

Wrong solu­tion.

This fails if a word is sub­set of another word.
{men, men­tor, tor­ment, man, .…}
Word to search : “mentorman”.

• tuto­ri­al­hori­zon

The above exam­ple worked fine for me . The out­put was “men­tor man” , i think its a cor­rect outcome.