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"

String ="thisisadog"

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<String> hs) {
if (find(s, hs, "")) {
} else {
System.out.println("Cant Break");
}
}
public boolean find(String s, HashSet<String> 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<String> hs = new HashSet<String>();
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.

Word Break Problem - Overlapping Subproblems
Word Break Problem – Overlapping Subproblems

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<String> dict,
HashSet<String> 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<String> hs = new HashSet<String>();
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<String> memoization = new HashSet<String>();
ws.findUsingDP(s, hs, memoization, "");
}
}

view raw
WordBreak.java
hosted with ❤ by GitHub

Output:
this is sumit jain