# The Word Break Problem

Objective : Given an string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words.

Example:

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

String = "IamSumit"

Output: "I am Sumit"

Output : String can't be broken
```

Approach: Backtracking- Naive Approach

• Navigate the given input string.
• Take a blank string and keep adding one character at a time to it.
• Keep checking if the word exist in the dictionary.
• If word exist in the dictionary then add that word to the answer string and make recursive call to the rest of the string.
• If any of the recursive call returns false then backtrack and remove the word from the answer string and again keep adding the characters to string.
• If all the recursive calls return true that means string has been broken successfully.
• See the code for better explanation.

Complete Code:

If we notice here we aresolving many sub-problems repeatedly.

Dynamic Programming 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.
• Whenever any recursive call returns false, store that string in HashMap.
• See the code for better explanation

Complete Code:

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

### 9 thoughts on “The Word Break Problem”

1. Can you give an input example using which Line 10, 11 will be used in the DP approach

2. Both recursion and DP appear to be overkill to me. You just scan through the string and just if a substring (i to the end) is in the dictionary. If not, just stop and return false. If a word is found, then keep scanning the rest. Actually memoization is useless. It depends on the dictionary is a list or a hash table.

• exactly when i read the problem the same thing came to my mind. we just need to scan through the dictionary and check whether dictionary[i] is a substring in the word . and keep on doing this until the length matches. the there is no point going for recursion unless you want to waste your time.

3. This approach is just recursion way of solving problem. There is no backtracking here.

• Backtracking 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 recursive function for that. Its a Top-Down DP approach.

4. Wrong solution.

This fails if a word is subset of another word.
{men, mentor, torment, man, ….}
Word to search : “mentorman”.