This post is completed by 1 user

  • 0
 Add to List
Hard

The Word Break Problem

Objective: Given a 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 exists in the dictionary.
  • If a word exists in the dictionary then add that word to the answer string and make a recursive call to the rest of the string.
  • If any of the recursive calls return false then backtrack and remove the word from the answer string and again keep adding the characters to the string.
  • If all the recursive calls return true that means the string has been broken successfully.
  • See the code for a better explanation.

Code:


If we notice here we are solving 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 a better explanation

Code:


Output:

Output:
this is sumit jain

Also Read: