# 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:

 import java.util.HashSet; public class WordBreakRecursion { public void wordBreak(String s, HashSet hs) { if (find(s, hs, "")) { } else { System.out.println("Cant Break"); } } public boolean find(String s, HashSet dict, String answer) { // System.out.println(s + " " + answer); if (s.length() == 0) { System.out.println(answer); return true; } else { int index = 0; String word = ""; while (index < s.length()) { word += s.charAt(index);// add one char at a time // check if word exists in dictionary if (dict.contains(word)) { //add word to the answer and make a recursive call if (find(s.substring(index + 1), dict, answer + word + " ")) { return true; } else { //System.out.println(word + " backtrack"); index++; } } else { index++; } } return false; } } public static void main(String[] args) { HashSet hs = new HashSet(); hs.add("this"); hs.add("is"); hs.add("sumit"); hs.add("jain"); hs.add("the"); hs.add("problem"); String s = "thisissumitjain"; WordBreakRecursion ws = new WordBreakRecursion(); ws.wordBreak(s, hs); } }

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:

 import java.util.HashSet; public class WordBreak { public boolean findUsingDP(String s, HashSet dict, HashSet memory, String answer) { if (s.length() == 0) { System.out.println(answer); return true; } else if (memory.contains(s)) { return false; } else { int index = 0; String word = ""; while (index < s.length()) { word += s.charAt(index);// add one char at a time // check if word already being solved if (dict.contains(word)) { if (findUsingDP(s.substring(index + 1), dict, memory, answer + word + " ")) { return true; } else { System.out.println("backtrack"); index++; } } else { index++; } } memory.add(s);// memoization for future; return false; } } public static void main(String[] args) { HashSet hs = new HashSet(); hs.add("this"); hs.add("is"); hs.add("sumit"); hs.add("jain"); hs.add("the"); hs.add("problem"); String s = "thisissumitjain"; WordBreak ws = new WordBreak(); // create another HashSet so store the sub problems result HashSet memoization = new HashSet(); ws.findUsingDP(s, hs, memoization, ""); } }

view raw
WordBreak.java
hosted with ❤ by GitHub

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