Last Updated: 23 Dec, 2020
Word Break II
Hard
Asked in companies
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
Approaches
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.
Algorithm:
- 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 it is present in the HashSet:
- If none of the substrings of sentences are present in the HashSet, then there are no sentences possible from the current string.
- Start exploring every substring from the start of the string and check if it is in the HashSet.
- Return all the valid output sentences.
We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again.
Lets understand by an example:
Suppose our string ‘S’ is “aakash”
The below figure shows some of the recursive calls made for the given problem.
As we can see, some subproblems are called multiple times.
Same subproblems are shown by the same color.
That’s why we are storing the solved subproblems in a map so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the map.
Algorithm:
- Use a map that contains a list of all the valid sentences that can be formed with a substring of the sentence from “index” to “sentence.size()-1”.
- Before calling the recursive function for any “index” of sentences, check whether we have any solution for that or not?
- If we have already a solution for current “index” in our map, then simply return the solution corresponding to the current “index”,
- Else we will solve the problem.
- Start exploring every substring from the “index” of the string till the end and check if it is in the dictionary.
- If it is present in the dictionary:
- Check if it is possible to form the rest of the sentence using dictionary words. If yes, you append the current “word” to all the substrings which are possible to make the rest of the sentences.
- If it is present in the dictionary:
- If none of the substrings of sentences is present in the dictionary, then there are no sentences possible from the current “index”.
- Start exploring every substring from the “index” of the string till the end and check if it is in the dictionary.
- And finally, before returning the answer, we will save it on the map for later use.
The idea is to use Trie data structure.
A trie is a tree-like data structure whose nodes store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree.
Using trie will help us to save time and space.
A sample trie formed by adding words ‘ate’, ‘ant’, ‘ants’, ‘bat’, ‘ball’, ‘and’ is shown below. The nodes with green color represent the end of the word.
Algorithm:
- Generate a trie by adding the words of the dictionary. The last letter of each word should be marked as the terminal or end of the word.
- After trie is built, string ‘S’ can be easily compared letter by letter in the trie.
- Traverse the string ‘S’ from left to right:
- If the current character is not present as the children of the root of the trie, return from here as we can’t break the given string in valid words.
- If at any point, we encounter a leaf in the trie, we can assume that we have found a valid word in the dictionary.
- If we reach the end of the string ‘S’, we will add the sentence formed by breaking the string ‘S’ to our output array.
- Else, recursively try to break the remaining string.
- Return the output array containing all the possible sentences obtained from breaking the given string ‘S’.
Similar problems