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

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

%d bloggers like this: