The same word from a dictionary can be used as many times as possible to make sentences.
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.
Print each possible sentence after adding spaces in different lines.
You do not need to print anything, it has already been taken care of. Order of sentences does not matter.
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.
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:
While exploring all possibilities, we are also going to store whatever solution we got till now for a sentence so that we will be able to avoid redundant function calls.
Algorithm Looks Like:
unordered_map<int,vector<string>> dp
dp[index] contains a list of all the valid sentences that can be formed with a substring of the sentence from “index” to “sentence.size()-1”.
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.
To know more about tries, click here.
Algorithm: