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:


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:

Output:
this is sumit jain

9 thoughts on “The Word Break Problem”

  1. 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.

    Reply
    • 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.

      Reply
    • 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.

      Reply
  2. Wrong solution.

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

    Reply
    • The above example worked fine for me . The output was “mentor man” , i think its a correct outcome.

      Reply
  3. Hi, for the example given with findUsingDP() method get total 5 recursive call with adding to memory… by this way if we change the input string from “thisissumitjain” to “thisissumitjainthisissumitjain” which is double of same string then we need to get final output with 5+1=6 recursive calls by using suffix from memory and need to reduce the method call. But here no where we are using memory read since its add at last and in future never comes….

    Reply

Leave a Reply to Rahul Shukla Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.