Given a string and set of dictionary words, determine if string can be segmented into a space-separated sequence of one or more dictionary words.



Dictionary Words: {“A”, “AN”, “AND”, “DROID”, “ANDROID”,”I”, “LOVE”, “SRC”}

Output: true (As it can be separated as “I LOVE ANDROID SRC” or “I LOVE AN DROID SRC”)

For finding if it is possible to separate given string, we look at each prefix and search it in dictionary . If current prefix is found in dictionary, we repeat for rest of the substring. If we get true for rest string as well, answer is yes, or else we check for next prefix. If we have finished checking all prefixes and none of them resulted in a solution, result is  false.

Let’s consider above example “ILOVEANDROIDSRC”

We will first check for “I”, it is present in dictionary. We will check for “LOVEANDROIDSRC”. While processing once we get that “LOVE” is  a dictionary word. We process for rest of it “ANDROISRC” and so on and finally return result.

Above process is of checking dictionary word is repeated again. It has overlapping sub-problems. Lets understand with example of “android”.

From above partially completed recursion tree for checking prefixes, it can be observed that it is checking again for same yellow marked words in dictionary. We can improve it using memoization, we will store result in an array after one lookup in dictionary and will avoid repetition in checking

Complete Source Code for Word Break Problem in Java

Leave a Reply

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