Word Break II

Posted: 23 Dec, 2020
Difficulty: Hard


Try Problem

You are given a non-empty string S containing no spaces’ and a dictionary 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 ‘S’, such that each word in a sentence exists in the given dictionary.

Note :

The same word in the dictionary can be used multiple times to make sentences.
Assume that the dictionary does not contain duplicate words.

Input format :

The first line contains an integer ‘T’ denoting the number of test cases. 

Then the 'T' test cases follow.

The first line contains an integer value ‘K’ which denotes the size of the dictionary.

The second line contains ‘K’ non-empty, space separated strings denoting the words of the dictionary.

The third line contains a non-empty string ‘S’.

Output format :

For each test case, print each possible sentence after adding spaces, in different lines.

The output of each test case is printed in a separate line. 
Note :
1. You do not need to print anything, it has already been taken care of. Just implement the given function.
2. The order in which the output sentences are returned does not matter.
Constraints :
1 <= T <= 10
1 <= K <= 100
1 <= | word | <= 16
1 <= | S | <= 13

where |word| is the length of each word in the dictionary and |S| is the length of the string S.

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.


  • Store all words of the dictionary in a set to speed up the process of checking whether a current word exists in the dictionary or not.
  • Base condition, If we have checked for all the substrings, then just return with a list containing only a null string
  • Else,
    • Start exploring every substring from the start of the string and check if it is in the HashSet.
      • If it is present in the HashSet:
        • 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 substrings possible from the rest of the sentences.
    • If none of the substrings of sentences are present in the HashSet, then there are no sentences possible from the current string.
  • Return all the valid output sentences.
Try Problem