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
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...read more
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 m...read more
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’.
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: OtherExplanation: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.
Java (SE 1.8)
/*
Time Complexity : O(N * (2 ^(N - 1))
Space Complexity : O(26 * K * | word |)
Where 'N' is the length of string 'S', 'K' is the number of words in the dictionary and | word | is the length of each word.
*/
import java.util.ArrayList;
class TrieNode
{
TrieNode[] children;
boolean isTerminal;
TrieNode()
{
children = new TrieNode[26];
isTerminal = false;
for (int i = 0; i < 26; i++)
children[i] = null;
}
}
public class Solution
{
public static void insert(TrieNode root, String word)
{
TrieNode curr = root;
for (int i = 0; i < word.length(); i++)
{
// Expanding the Trie if the branch was not there yet
if (curr.children[word.charAt(i) - 'a'] == null)
{
curr.children[word.charAt(i) - 'a'] = new TrieNode();
}
curr = curr.children[word.charAt(i) - 'a'];
}
// Mark last node as leaf
curr.isTerminal = true;
}
public static void search(TrieNode root, String s, ArrayList res, String temp, int pos)
{
TrieNode curr = root;
for (int i = pos; i < s.length(); i++)
{
if (curr.children[s.charAt(i) - 'a'] == null)
{
return;
}
if (curr.children[s.charAt(i) - 'a'].isTerminal == true)
{
// Last word we found with a positive lookup
String lastWord = temp;
lastWord += (s.substring(pos, i + 1));
// If it is also the last character of s, update res
if (i == s.length() - 1)
{
res.add(lastWord);
}
// Recursive calls otherwise
else
{
search(root, s, res, lastWord + " ", i + 1);
}
}
curr = curr.children[s.charAt(i) - 'a'];
}
return;
}
public static ArrayList wordBreak(String s, ArrayList dictionary)
{
// Base Trie
TrieNode root = new TrieNode();
// Add dictionary words into trie
for (int i = 0; i < dictionary.size(); i++)
{
insert(root, dictionary.get(i));
}
// Computing the final result
ArrayList res = new ArrayList<>();
search(root, s, res, "", 0);
return res;
}
} Python (3.5)
'''
Time Complexity : O(N * (2 ^(N - 1))
Space Complexity : O(26 * K * | word |)
Where N is the length of string 'S', 'K' is the number of words in the dictionary and
| word | is the length of each word.
'''
class TrieNode:
def __init__(self):
# Setting all children of a new trie node to None
self.children = [None for i in range(26)]
self.isTerminal = False
def insert(root, word):
curr = root
for i in range(len(word)):
# Expanding the Trie if the branch was not there yet
if (curr.children[ord(word[i]) - ord('a')] == None):
curr.children[ord(word[i]) - ord('a')] = TrieNode()
curr = curr.children[ord(word[i]) - ord('a')]
# Mark last node as leaf
curr.isTerminal = True
def search(root, s, res, temp, pos):
curr = root
for i in range(pos, len(s)):
if (curr.children[ord(s[i]) - ord('a')] == None):
return
if (curr.children[ord(s[i]) - ord('a')].isTerminal == True):
# Last word we found with a positive lookup
lastWord = temp
lastWord += s[pos: i + 1]
# If it is also the last character of s, update res
if (i == len(s) - 1):
res.append(lastWord)
# Recursive calls otherwise
else:
search(root, s, res, lastWord + " ", i + 1)
curr = curr.children[ord(s[i]) - ord('a')]
return
def wordBreak(s, dictionary):
# Base Trie
root = TrieNode()
# Add dictionary words into trie
for i in range(len(dictionary)):
insert(root, dictionary[i])
# Computing the final result
res = []
search(root, s, res, "", 0)
return res
C++ (g++ 5.4)
/*
Time Complexity : O(N * (2 ^(N - 1))
Space Complexity : O(26 * K * | word |)
Where N is the length of string 'S', 'K' is the number of words in the dictionary and | word | is the length of each word.
*/
class TrieNode
{
public:
TrieNode *children[26];
bool isTerminal;
TrieNode()
{
// Setting all children of a new trie node to NULL
for (int i = 0; i < 26; i++)
{
children[i] = NULL;
}
this->isTerminal = false;
}
};
void insert(TrieNode *root, string word)
{
TrieNode *curr = root;
for (int i = 0; i < word.size(); i++)
{
// Expanding the Trie if the branch was not there yet
if (curr->children[word[i] - 'a'] == NULL)
{
curr->children[word[i] - 'a'] = new TrieNode();
}
curr = curr->children[word[i] - 'a'];
}
// Mark last node as leaf
curr->isTerminal = true;
}
void search(TrieNode *root, string &s, vector &res, string temp, int pos)
{
TrieNode *curr = root;
for (int i = pos; i < s.size(); i++)
{
if (curr->children[s[i] - 'a'] == NULL)
{
return;
}
if (curr->children[s[i] - 'a']->isTerminal == true)
{
// Last word we found with a positive lookup
string lastWord = temp;
lastWord.append(s.substr(pos, i - pos + 1));
// If it is also the last character of s, update res
if (i == s.size() - 1)
{
res.push_back(lastWord);
}
// Recursive calls otherwise
else
{
search(root, s, res, lastWord + " ", i + 1);
}
}
curr = curr->children[s[i] - 'a'];
}
return;
}
vector wordBreak(string &s, vector &dictionary)
{
// Base Trie
TrieNode *root = new TrieNode();
// Add dictionary words into trie
for (int i = 0; i < dictionary.size(); i++)
{
insert(root, dictionary[i]);
}
// Computing the final result
vector res;
search(root, s, res, "", 0);
return res;
} Top TCS System Engineer Specialist interview questions & answers
Reviews
Interviews
Salaries
Users/Month
Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.
