Search Suggestions System

111k
0

Given an array of product names and a string searchWord, return the product suggestions after each character of searchWord is typed. For every prefix formed while typing, suggest at most three product names that start with that prefix. If more than three products match, return the three lexicographically smallest ones. Return the suggestions as a list of lists, where the i-th list contains the suggestions after typing the first i characters.

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: After typing m and mo, the first three matching products in sorted order are mobile, moneypot, and monitor. After typing mou, mous, and mouse, only mouse and mousepad still match.

Example 2

Input: products = ["havana"], searchWord = "havana"

Output: [["havana"], ["havana"], ["havana"], ["havana"], ["havana"], ["havana"]]

Explanation: Only one product exists, so that same product is suggested after every typed character.

Brute Force Approach

The most direct thought is this: after each new character is typed, build the current prefix and check every product to see whether it starts with that prefix. That works because the problem only asks for matching products with the same beginning. Sorting the products first helps this simple idea a lot. Once the array is sorted, the first matching products found during scanning are already the lexicographically smallest ones. So the brute-force version can stop after collecting three matches for each prefix.

Algorithm

  • First, sort the products array in lexicographical order. This is done so matching products appear in the correct dictionary order from the very beginning.

  • Keep an empty string called prefix and grow it one character at a time using searchWord. This matters because suggestions are needed after every typed character, not only for the full word.

  • For each new prefix, scan the full products array from left to right. This direct scan checks every product that might match the current prefix.

  • If a product starts with the current prefix, add it to the current suggestion list. Because the array is sorted, the first matches found are already the smallest valid answers.

  • Stop collecting once three products are stored, because the problem never asks for more than three suggestions.

  • Add the current suggestion list to the final answer and continue with the next longer prefix.

  • After all prefixes are processed, return the final list of suggestion lists.

Dry Run

Search Suggestions System Brute Dry Run

Search Suggestions System Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks whether the given product starts with the current prefix.
bool startsWithPrefix(const string& product, const string& prefix) {
// A shorter word can never contain a longer prefix at its start.
if (product.length() < prefix.length()) {
return false;
}
for (int i = 0; i < (int)prefix.length(); i++) {
// If any character differs, this product does not match the prefix.
if (product[i] != prefix[i]) {
return false;
}
}
return true;
}
public:
/*
Returns up to three lexicographically smallest suggestions
for every prefix of the search word.
*/
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
// Sort first so the first matches found are already in correct order.
sort(products.begin(), products.end());
// Stores the final answer for all typed prefixes.
vector<vector<string>> answer;
// Builds the prefix one character at a time.
string prefix = "";
for (char ch : searchWord) {
// Extend the current prefix because one more character was typed.
prefix += ch;
// Stores up to three matches for the current prefix.
vector<string> currentSuggestions;
for (const string& product : products) {
// Add only products that really start with the current prefix.
if (startsWithPrefix(product, prefix)) {
currentSuggestions.push_back(product);
}
// Stop early because keeping more than three suggestions is unnecessary.
if ((int)currentSuggestions.size() == 3) {
break;
}
}
// Save the suggestions for this typed prefix.
answer.push_back(currentSuggestions);
}
return answer;
}
};
// Driver code starts
int main() {
vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};
string searchWord = "mouse";
Solution obj;
vector<vector<string>> answer = obj.suggestedProducts(products, searchWord);
for (const vector<string>& suggestions : answer) {
cout << "[";
for (int i = 0; i < (int)suggestions.size(); i++) {
cout << suggestions[i];
if (i + 1 < (int)suggestions.size()) {
cout << ", ";
}
}
cout << "]" << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N x log N + (M x N x P)), where N is the number of products, M is the length of searchWord, and P is the average prefix-check cost. Sorting takes O(N x log N), and each prefix may scan all products.

Space Complexity: O(1) extra space apart from the output, because only a few variables are used while scanning.

Optimal Approach

The important observation is that each prefix of searchWord needs only three answers, not the full list of matching products. That matters because if a trie node stores only the best three suggestions for its prefix, then later search becomes very small and direct. Sorting the products first gives the next key idea. Once the products are sorted, the first products inserted into a trie path are already the lexicographically smallest ones for that prefix. So if each trie node stores at most three products while inserting sorted words, every node automatically keeps exactly the suggestions that the problem wants.

Algorithm

  • First, sort the products array in lexicographical order. This is done so the earliest products seen during insertion are already the smallest dictionary-order choices for every prefix.

  • Create a trie where each node stores two things: its child links and a small list of up to three suggested products. This matters because later search should answer each prefix directly without scanning all matching products again.

  • Insert each sorted product into the trie character by character. While moving through the path, add the current product to the node's suggestion list only if that list still has fewer than three products.

  • Keeping only three products at each node is enough because the problem never asks for more than three suggestions, so storing extra words would only waste space.

  • After the trie is built, start from the root and read searchWord one character at a time. This matches the way the suggestions are shown after each typed character.

  • If the next child for the current character does not exist, no later prefix can match either, so add empty lists for this and all remaining characters.

  • If the child exists, move to that node and copy its stored suggestion list into the answer. This works because that node already represents the exact current prefix.

  • Continue until all characters are processed, then return the full list of suggestions.

Key Points

  • Sorting is what makes the stored suggestions automatically lexicographically correct.

  • Once a prefix fails in the trie, all longer prefixes must also fail.

  • Each trie node stores only up to three products, not all matching products.

Dry Run

Search Suggestions System Optimal Dry Run

Search Suggestions System Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class TrieNode {
public:
vector<TrieNode*> children;
vector<string> suggestions;
// Creates one trie node with empty child links and no suggestions yet.
TrieNode() {
// Reserve one child slot for each lowercase English letter.
children.assign(26, nullptr);
// Start with no stored suggestions for this prefix.
suggestions.clear();
}
};
class Solution {
private:
// Inserts one sorted product into the trie and updates prefix suggestions.
void insertProduct(TrieNode* root, const string& product) {
// Start insertion from the trie root.
TrieNode* node = root;
for (char ch : product) {
// Convert the current character into a trie index from 0 to 25.
int index = ch - 'a';
// Create a new node only when this prefix path appears for the first time.
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
}
// Move to the node that represents the current prefix.
node = node->children[index];
// Store this product only while the node still needs suggestions.
if ((int)node->suggestions.size() < 3) {
node->suggestions.push_back(product);
}
}
}
public:
/*
Returns up to three lexicographically smallest suggestions
for every prefix of the search word.
*/
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
// Sort first so inserted products naturally fill each node with smallest answers.
sort(products.begin(), products.end());
// Create one trie that stores prefix suggestions for all products.
TrieNode* root = new TrieNode();
// Insert every sorted product into the trie.
for (const string& product : products) {
insertProduct(root, product);
}
// Stores the final answer for each typed prefix.
vector<vector<string>> answer;
// Start searching from the trie root.
TrieNode* node = root;
for (char ch : searchWord) {
// If a prefix already failed earlier, all later prefixes also fail.
if (node == nullptr) {
answer.push_back({});
continue;
}
// Convert the current character into a trie index from 0 to 25.
int index = ch - 'a';
// Move to the node for the new longer prefix.
node = node->children[index];
// Add empty suggestions when this prefix does not exist in the trie.
if (node == nullptr) {
answer.push_back({});
} else {
// Use the stored top suggestions because they already match this prefix.
answer.push_back(node->suggestions);
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<string> products = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};
string searchWord = "mouse";
Solution obj;
vector<vector<string>> answer = obj.suggestedProducts(products, searchWord);
for (const vector<string>& suggestions : answer) {
cout << "[";
for (int i = 0; i < (int)suggestions.size(); i++) {
cout << suggestions[i];
if (i + 1 < (int)suggestions.size()) {
cout << ", ";
}
}
cout << "]" << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O((N x log N) + L + M), where N is the number of products, L is the total number of characters across all products, and M is the length of searchWord. Sorting takes O(N x log N), trie insertion takes O(L), and processing the search word takes O(M).

Space Complexity: O(L), because the trie stores product characters across all inserted words, and each node keeps only up to three suggestions.

Interview follow-up Questions

Sorting makes the smallest lexicographical products appear first. That is why both approaches can return correct suggestions in dictionary order without extra sorting for each prefix.

TrieSortingArraysData Structures

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. tuf-examples-1 Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 ,...

76.5k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Comments0