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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • Rahul Shukla

    http://www.ideserve.co.in/learn/word-break-problem
    Here is a nice explanation of the algorithm.

  • CRH

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

  • John

    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

      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.

  • MURHY

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

    • tutorialhorizon

      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.

  • rai.kaushal

    Wrong solution.

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

    • tutorialhorizon

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

%d bloggers like this: