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.


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:

this is sumit jain

9 Responses

  1. Rahul Shukla says:
    Here is a nice explanation of the algorithm.

  2. CRH says:

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

  3. John says:

    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.

    • biswajit singh says:

      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.

  4. MURHY says:

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

    • tutorialhorizon says:

      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.

  5. rai.kaushal says:

    Wrong solution.

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

    • tutorialhorizon says:

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

  6. Anand Kumar says:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

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

%d bloggers like this: