Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

The Word Break Problem

Objec­tive : Given an string and a dic­tio­nary of words, find out if the input string can be bro­ken into a space-separated sequence of one or more dic­tio­nary words.

Exam­ple:

dictionary = ["I" , "have", "Jain", "Sumit", "am", "this", "dog"]

String = "IamSumit"

Output: "I am Sumit"

String ="thisisadog"

Output : String can't be broken

Approach: Back­track­ing– Naive Approach

  • Nav­i­gate the given input string.
  • Take a blank string and keep adding one char­ac­ter at a time to it.
  • Keep check­ing if the word exist in the dictionary.
  • If word exist in the dic­tio­nary then add that word to the answer string and make recur­sive call to the rest of the string.
  • If any of the recur­sive call returns false then back­track and remove the word from the answer string and again keep adding the char­ac­ters to string.
  • If all the recur­sive calls return true that means string has been bro­ken successfully.
  • See the code for bet­ter explanation.

Com­plete Code:

If we notice here we are­solv­ing many sub-problems repeatedly.

Word Break Problem - Overlapping Subproblems

Word Break Prob­lem — Over­lap­ping Subproblems

Dynamic Pro­gram­ming 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.
  • When­ever any recur­sive call returns false, store that string in HashMap.
  • See the code for bet­ter explanation

Com­plete Code:

Output:
this is sumit jain

You may also like...

  • Rahul Shukla

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

  • CRH

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

  • John

    Both recur­sion and DP appear to be overkill to me. You just scan through the string and just if a sub­string (i to the end) is in the dic­tio­nary. If not, just stop and return false. If a word is found, then keep scan­ning the rest. Actu­ally mem­o­iza­tion is use­less. It depends on the dic­tio­nary is a list or a hash table.

    • biswa­jit singh

      exactly when i read the prob­lem the same thing came to my mind. we just need to scan through the dic­tio­nary and check whether dictionary[i] is a sub­string in the word . and keep on doing this until the length matches. the there is no point going for recur­sion unless you want to waste your time.

  • MURHY

    This approach is just recur­sion way of solv­ing prob­lem. There is no back­track­ing here.