In this guide, you will get 1268. Search Suggestions System LeetCode Solution with the best time and space complexity. The solution to Search Suggestions System problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an array of strings products and a string searchWord.
Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
Example 1:
Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse”
Output: [[“mobile”,”moneypot”,”monitor”],[“mobile”,”moneypot”,”monitor”],[“mouse”,”mousepad”],[“mouse”,”mousepad”],[“mouse”,”mousepad”]]
Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”].
After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”].
After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”].
Example 2:
Input: products = [“havana”], searchWord = “havana”
Output: [[“havana”],[“havana”],[“havana”],[“havana”],[“havana”],[“havana”]]
Explanation: The only word “havana” will be always suggested while typing the search word.
Constraints:
1 <= products.length <= 1000
1 <= products[i].length <= 3000
1 <= sum(products[i].length) <= 2 * 104
All the strings of products are unique.
products[i] consists of lowercase English letters.
1 <= searchWord.length <= 1000
searchWord consists of lowercase English letters.
1268. Search Suggestions System LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
const string* word = nullptr;
TrieNode() : children(26) {}
};
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products,
string searchWord) {
vector<vector<string>> ans;
for (const string& product : products)
insert(product);
shared_ptr<TrieNode> node = root;
for (const char c : searchWord) {
if (node == nullptr || node->children[c - 'a'] == nullptr) {
node = nullptr;
ans.push_back({});
continue;
}
node = node->children[c - 'a'];
ans.push_back(search(node));
}
return ans;
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (const char c : word) {
const int i = c - 'a';
if (node->children[i] == nullptr)
node->children[i] = make_shared<TrieNode>();
node = node->children[i];
}
node->word = &word;
}
vector<string> search(shared_ptr<TrieNode> node) {
vector<string> res;
dfs(node, res);
return res;
}
void dfs(shared_ptr<TrieNode> node, vector<string>& ans) {
if (ans.size() == 3)
return;
if (node == nullptr)
return;
if (node->word != nullptr)
ans.push_back(*node->word);
for (shared_ptr<TrieNode> child : node->children)
dfs(child, ans);
}
}; /* code provided by PROGIEZ */
1268. Search Suggestions System LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String word;
}
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> ans = new ArrayList<>();
for (final String product : products)
insert(product);
TrieNode node = root;
for (final char c : searchWord.toCharArray()) {
if (node == null || node.children[c - 'a'] == null) {
node = null;
ans.add(new ArrayList<>());
continue;
}
node = node.children[c - 'a'];
ans.add(search(node));
}
return ans;
}
private TrieNode root = new TrieNode();
private void insert(final String word) {
TrieNode node = root;
for (final char c : word.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
}
node.word = word;
}
private List<String> search(TrieNode node) {
List<String> res = new ArrayList<>();
dfs(node, res);
return res;
}
private void dfs(TrieNode node, List<String> ans) {
if (ans.size() == 3)
return;
if (node == null)
return;
if (node.word != null)
ans.add(node.word);
for (TrieNode child : node.children)
dfs(child, ans);
}
} // code provided by PROGIEZ
1268. Search Suggestions System LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: dict[str, TrieNode] = {}
self.word: str | None = None
class Solution:
def suggestedProducts(self, products: list[str],
searchWord: str) -> list[list[str]]:
ans = []
root = TrieNode()
def insert(word: str) -> None:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
def search(node: TrieNode | None) -> list[str]:
res: list[str] = []
dfs(node, res)
return res
def dfs(node: TrieNode | None, res: list[str]) -> None:
if len(res) == 3:
return
if not node:
return
if node.word:
res.append(node.word)
for c in string.ascii_lowercase:
if c in node.children:
dfs(node.children[c], res)
for product in products:
insert(product)
node = root
for c in searchWord:
if not node or c not in node.children:
node = None
ans.append([])
continue
node = node.children[c]
ans.append(search(node))
return ans # code by PROGIEZ
