Word Break-1

Posted: 23 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a non-empty string containing no spaces (say sentence) and a dictionary of list of non-empty strings (say the list of words). You are supposed to construct and return all possible sentences after adding spaces in the originally given string (sentence), where each word must exist in the given dictionary.

Note :
The same word from a dictionary can be used as many times as possible to make sentences.
Input format :
The first line contains an integer value ‘N’ which denotes the size of the dictionary.
Next ‘N’ line contains a non-empty string “denoting words”.
Next ‘(N+1)’ th line contains a non-empty string without any space.
Output format :
Print each possible sentence after adding spaces in different lines.
Note :
You do not need to print anything, it has already been taken care of. Order of sentences does not matter.
Constraints :
1 <= N <= 100
1 <= M <= 16
1 <= W <= 16
Where ‘N’ is the length of a dictionary , ‘W’ is the length of the “word” in a dictionary and ‘M’ is the length of a sentence.
Time limit: 1 sec.
Approach 1

We need to keep exploring the given string from current position ‘i’ to until we wouldn’t find a position such that substring ‘i’ to ‘j’ exists in the dictionary.

The algorithm looks like:

  1. Store all words of the dictionary in unordered_map to speed up checking whether a current word exists in the dictionary or not?
  2. If sentence size is ended then just return with a null string of list.
  3. Else,
    1. You start exploring every substring from the start of the string and check if it is in the dictionary.
      1. If it is
        1. Then you check if it is possible to form the rest of the sentence using dictionary words. If yes, you append the current substring to all the substring possible from the rest of the sentences.
    2. If none of the substrings of sentences are present in the dictionary, then there are no sentences possible from the current string.
Try Problem