Word Break-1
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

Question

Word Break-1

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.

Accepted Answer

Brute Force Approach

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,
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.

Space Complexity: O(1)Explanation:

O(N*(2^N)), where ‘N’ is the length of the sentence.

Space complexity would be O(N*(2^N)) because in the worst case, we will have to store all possible combinations for all indexes to print the output. So there will be total ‘N’ indexes, and each index can have an O(2^N) combination of sentences. So overall space complexity will be O(N*(2^N)).

Time Complexity: O(1)Explanation:

O(N*(2^N)), where ‘N’ is the length of the sentence.

Time complexity would be O(N*(2^N)) because every position we will have two choices, whether we can include it or not. And for a single option, we will have to put it into the list which will cost ‘N’.

Accepted Answer

Dynamic Programming Approach

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> 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”.

Before calling the recursive function for any “index” of sentences, we should check whether we have any solution for that or not?
1. 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.
1. You start exploring every substring from the “index” of the string till the end 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 “word” to all the substrings which are possible to make the rest of the sentences.
2. If none of the substrings of sentences is present in the dictionary, then there are no sentences possible from the current “index”.
And finally, before returning the answer, we will save it in “dp” for later use.

Space Complexity: O(1)Explanation:

O(N*(2^N)), where ‘N’ is the length of the sentence.

Space complexity would be O(N*(2^N)) because in the worst case “dp” will store all possible combinations for all indexes. So there will be total ‘N’ indexes, and each index has an O(2^N) combination of sentences. So overall space complexity will be O(N*(2^N)). Similarly, we will have to store all possible combinations of sentences for all indexes to print the output.

Time Complexity: O(1)Explanation:

O(N*(2^N)), where ‘N’ is the length of the sentence.

Time complexity would be in worst case O(N*(2^N)) when only all the combination of sentence exist in the dictionary like

sentence=”xxx” dictionary={“x”,”xx”,”xxx”}. We need to explore the possible combinations. While our “dp” is avoiding many redundant function calls, but still this approach will also go in O(N*(2^N)) in worst case.

Accepted Answer

Trie based Approach

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’.

Space Complexity: O(1)Explanation:

O(26 * K * | word |), where K is the number of strings in the dictionary, and | word | is the length of a word in the dictionary.

In the worst case, for every word in the dictionary, we will create | word | nodes and every node will have an array of size 26 (to store the children of the node). Since there are K strings in the dictionary, the number of nodes will be O(K * | word |) and thus the total space complexity will be O(26 * K * | word |).

Recursion stack space of O(N) is also used. Thus, the final space complexity is O((26 * K * | word |) + N) = O(26 * K * | word |).

Time Complexity: O(1)Explanation:

O(N * (2 ^ (N - 1)), where ‘N’ is the length of the sentence.

Time complexity would be, in the worst case, O(N * (2 ^ (N - 1))) when each substring of the sentence exists as a word in the dictionary like sentence = “xxx” and dictionary={“x”, “xx”, “xxx”}. We need to explore the possible combinations. While our map is avoiding many redundant function calls, but still this approach will also go in O(N * (2 ^ (N - 1))) in the worst case. Though the complexity of this approach is the same as the previous approach, yet this approach is better because the time taken to search for a word in the trie is much less than that in a hashset.

Note :

Input format :

Output format :

Note :

Constraints :

Top Groww Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern