Word Break-1
Last Updated: 23 Sep, 2020
Difficulty: Moderate
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:
- Store all words of the dictionary in unordered_map to speed up checking whether a current word exists in the dictionary or not?
- If sentence size is ended then just return with a null string of list.
- Else,
- You start exploring every substring from the start of the string and check if it is in the dictionary.
- If it is
- 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.
- If it is
- If none of the substrings of sentences are present in the dictionary, then there are no sentences possible from the current string.
- You start exploring every substring from the start of the string and check if it is in the dictionary.
Approach 2
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:
- Let’s say
unordered_map<int,vector<string>> dpdp[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”.
- Before calling the recursive function for any “index” of sentences, we should check whether we have any solution for that or not?
- If we have already a solution for current “index” in “dp” then simply return the solution corresponds to the current “index”,
- Else we will solve the problem.
- You start exploring every substring from the “index” of the string till the end and check if it is in the dictionary.
- If it is
- Then you 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
- If none of the substrings of sentences is present in the dictionary, then there are no sentences possible from the current “index”.
- You 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 in “dp” for later use.
Approach 3
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:
- 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’.
