1268. Search Suggestions System
Problem Description
This LeetCode problem involves creating an autocomplete system for a given list of products and a search word. The goal is to return a list of lists containing at most three suggested product names that share a common prefix with the progressively typed characters of the searchWord
. When multiple products share the same prefix, the top three suggestions should be the ones that are lexicographically smallest (i.e., alphabetically sorted).
Intuition
We start with the most natural approach to solving this kind of problem, which is by using a trie data structure. A trie is an efficient information retrieval data structure. Each node in the trie represents a different character of the alphabet, and each path down the trie can be seen as a prefix of some word or a complete word.
-
Sorting the products: Our first step is to sort the list of
products
because this guarantees that any traversal in alphabetical order will satisfy the lexicographical requirement. -
Building the Trie:
- We create a trie and insert each product into it.
- As we insert each product, we keep track of the product index within the trie nodes (by appending the index to the node's value list) so we can later access them in sorted order.
- We limit the number of indices in the value list to three because only three suggestions are needed at max for each prefix.
-
Performing the Search:
- Now, for each character typed into the
searchWord
, we will traverse the trie. - If we find that there's no child node corresponding to the character, we break out of the loop since no product with such a prefix exists.
- Otherwise, we collect the indices (up to three) at every node that corresponds to the prefix made by the typed characters of searchWord so far.
- This gives us a list of lists of indices of product suggestions after each character of
searchWord
.
- Now, for each character typed into the
-
Generating the Result:
- Finally, we map the collected product indices to their respective strings.
- We do this by looking up each index in the sorted
products
array and returning the word at that index.
By the end of this process, we have our autocomplete system, where after each character is typed from the searchWord
, a list of up to three lexicographically smallest product suggestions is provided.
Learn more about Trie, Binary Search, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution approach leverages both Tries and sorting to efficiently handle the autocomplete system. Below is a step-by-step explanation of the algorithm, using the reference provided in the code snippet:
-
Tri-Node Definition:
- A Tri-node, represented by the
[Trie](/problems/trie_intro)
class, contains two main attributes:children
(an array that holds up to 26 child nodes, representing each letter of the alphabet) andv
(a list that will store indices of products up to three for the nodes relevant to the search). - The
children
array is initialized withNone
, indicating that initially, there are no child nodes.
- A Tri-node, represented by the
-
Inserting Products into Trie:
- The
insert
method is used to add products into the trie. - Each product is inserted character-by-character. For each character, the corresponding child node is either found or created.
- As we traverse through or create nodes for each character, we add the index of the product (coming from the enumeration of the sorted products list) into the
v
list of the node, ensuring we do not exceed three products.
- The
-
Searching the Trie:
- The
search
method is used to retrieve the list of product indices as per the characters of thesearchWord
. - It initializes an answer list
ans
of lists to store product indices for each character. - For each character in
searchWord
, the corresponding child index is calculated, and the traversal proceeds to the child if it exists. - If there is no such child, the autocomplete cannot proceed any further, and the loop breaks, leaving the remaining lists in
ans
empty. - For each existing node found via traversal, we collect up to three product indices represented by the node's
v
list and append it toans
.
- The
-
Constructing the Output:
- The
Solution
class has a method calledsuggestedProducts
, which puts the aforementioned[Trie](/problems/trie_intro)
class to use. - Initially, the list of
products
is sorted, which is a critical step to ensure that the indices stored in the trie's nodes will correspond to lexicographically sorted words. - For each product, it calls
insert
, passing the product and its index. - It then retrieves the list of suggestion indices for each character of the
searchWord
.
- The
-
Returning Product Suggestions:
- Finally, the list of suggestion indices is converted to the actual product strings. This is done using a list comprehension, which, for every list of product indices (
v
) resulted from the triesearch
, retrieves the product string from the sortedproducts
list. - The outer list comprehension is what generates the list of lists of product names, corresponding to each character of
searchWord
.
- Finally, the list of suggestion indices is converted to the actual product strings. This is done using a list comprehension, which, for every list of product indices (
This solution effectively uses the Trie data structure, coupled with careful handling of insertion and search operations and utilizing Python's list comprehensions, to solve the problem optimally and elegantly.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following example to illustrate the solution approach:
products
:["mobile","mouse","moneypot","monitor","mousepad"]
searchWord
:"mouse"
After applying the first step of sorting the products:
- Sorted
products
:["mobile","moneypot","monitor","mouse","mousepad"]
- Building the Trie: We insert each product into the Trie.
- Insert "mobile" at index 0: Node 'm' -> Node 'o' -> Node 'b' -> Node 'i' -> Node 'l' -> Node 'e'.
- Insert "moneypot" at index 1: Node 'm' -> Node 'o' -> Node 'n' -> Node 'e' -> Node 'y' -> Node 'p' -> Node 'o' -> Node 't'.
- Insert "monitor" at index 2: Node 'm' -> Node 'o' -> Node 'n' -> Node 'i' -> Node 't' -> Node 'o' -> Node 'r'.
- Insert "mouse" at index 3: Node 'm' -> Node 'o' -> Node 'u' -> Node 's' -> Node 'e'.
- Insert "mousepad" at index 4: Node 'm' -> Node 'o' -> Node 'u' -> Node 's' -> Node 'e' -> Node 'p' -> Node 'a' -> Node 'd'.
During insertion, each node keeps track of the indices of the products (up to 3) that pass through it.
-
Searching the Trie: We now search for each progressively typed prefix from the
searchWord
"mouse".- Search "m": Found node 'm' with product indices [0, 1, 2]. (Only the first 3 indices are considered for each node)
- Search "mo": Found node 'mo' with product indices [0, 1, 2].
- Search "mou": Found node 'mou' with product indices [3, 4].
- Search "mous": Found node 'mous' with product indices [3, 4].
- Search "mouse": Found node 'mouse' with product indices [3, 4].
-
Generating the Result: We will map the indices above to the product strings.
- The node for "m" gives us the indices [0, 1, 2] which correspond to the products:
["mobile","moneypot","monitor"]
. - The node for "mo" gives the same indices [0, 1, 2], so we get the same suggestions:
["mobile","moneypot","monitor"]
. - The node for "mou" gives us indices [3, 4], which map to:
["mouse","mousepad"]
. - The node for "mous" gives the same indices [3, 4], resulting in the same suggestions:
["mouse","mousepad"]
. - The node for "mouse" gives us indices [3, 4], leading to the same suggestions:
["mouse","mousepad"]
.
- The node for "m" gives us the indices [0, 1, 2] which correspond to the products:
The final output after each character is typed:
- After typing "m":
["mobile","moneypot","monitor"]
- After typing "mo":
["mobile","moneypot","monitor"]
- After typing "mou":
["mouse","mousepad"]
- After typing "mous":
["mouse","mousepad"]
- After typing "mouse":
["mouse","mousepad"]
This walk-through exemplifies the use of a trie data structure to support an efficient autocomplete system. With efficient insertion and search operations, as well as good use of sorting, the problem is solved optimally.
Solution Implementation
1from typing import List, Optional
2
3class Trie:
4 def __init__(self):
5 # Initialize each node with an array of 26 elements representing 26 characters, setting each to None.
6 # Each node stores a list of integer indices which represent suggested products.
7 self.children: List[Optional[Trie]] = [None] * 26
8 self.indices: List[int] = []
9
10 def insert(self, word: str, index: int):
11 # Insert a word into the trie with its associated product index.
12 node = self
13 for char in word:
14 char_index = ord(char) - ord('a')
15 if node.children[char_index] is None:
16 node.children[char_index] = Trie()
17 node = node.children[char_index]
18 # Insert product index into the current trie node's list if fewer than 3 suggestions.
19 if len(node.indices) < 3:
20 node.indices.append(index)
21
22 def search(self, word: str) -> List[List[int]]:
23 # Return a list of product index lists for each character in the searched word.
24 node = self
25 results = [[] for _ in range(len(word))]
26 for i, char in enumerate(word):
27 char_index = ord(char) - ord('a')
28 # Break early if no path in the trie exists for the current character.
29 if node.children[char_index] is None:
30 break
31 node = node.children[char_index]
32 # Add the current node's product indices to the results.
33 results[i] = node.indices
34 return results
35
36
37class Solution:
38 def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
39 # Sort products to ensure the lexicographically smallest suggestions.
40 products.sort()
41 trie = Trie()
42 # Insert each product into the trie along with its index.
43 for index, word in enumerate(products):
44 trie.insert(word, index)
45 # Get the list of product indices from the trie for each substring of the search word.
46 indices_list = trie.search(searchWord)
47 # Convert the list of product indices to a list of product strings.
48 return [[products[index] for index in indices_sublist] for indices_sublist in indices_list]
49
1// Trie data structure to hold prefixes and their associated indices
2class Trie {
3 Trie[] children = new Trie[26]; // Each child represents a letter 'a' to 'z'
4 List<Integer> indices = new ArrayList<>(); // List to hold indices of words where this node is a prefix
5
6 // Method to insert a word into the trie
7 public void insert(String word, int index) {
8 Trie node = this;
9 for (int j = 0; j < word.length(); ++j) {
10 int charIdx = word.charAt(j) - 'a'; // Calculate index of the character
11 if (node.children[charIdx] == null) {
12 node.children[charIdx] = new Trie();
13 }
14 node = node.children[charIdx];
15 // Only keep at most 3 indices in the list to meet problem constraints
16 if (node.indices.size() < 3) {
17 node.indices.add(index);
18 }
19 }
20 }
21
22 // Method to search in the trie and retrieve indices of entries with given prefix
23 public List<Integer>[] search(String word) {
24 Trie node = this;
25 int wordLength = word.length();
26 List<Integer>[] searchResults = new List[wordLength];
27 Arrays.setAll(searchResults, k -> new ArrayList<>());
28 for (int i = 0; i < wordLength; ++i) {
29 int charIdx = word.charAt(i) - 'a'; // Calculate index of the character
30 if (node.children[charIdx] == null) {
31 break; // No further matches, break out of the loop
32 }
33 node = node.children[charIdx]; // Move to the child node
34 searchResults[i] = node.indices; // Add the current node's indices
35 }
36 return searchResults;
37 }
38}
39
40class Solution {
41 // Method to suggest products based on the current searchWord input
42 public List<List<String>> suggestedProducts(String[] products, String searchWord) {
43 // Sort the products array to ensure the output is lexicographically sorted
44 Arrays.sort(products);
45 Trie trie = new Trie();
46
47 // Insert all products into the trie
48 for (int i = 0; i < products.length; ++i) {
49 trie.insert(products[i], i);
50 }
51
52 List<List<String>> suggestions = new ArrayList<>(); // Final list to hold the suggestions
53
54 // Search each prefix of the searchWord and construct the final suggestion list
55 for (List<Integer> indices : trie.search(searchWord)) {
56 List<String> productList = new ArrayList<>();
57 for (int index : indices) { // Convert the indices to actual product strings
58 productList.add(products[index]);
59 }
60 suggestions.add(productList);
61 }
62
63 return suggestions; // Return the accumulated list of product suggestions
64 }
65}
66
1class Trie {
2public:
3 // Function to insert a word into the Trie
4 void Insert(string &word, int wordIndex) {
5 Trie* node = this; // Start from the root node
6 for (char ch : word) { // Loop through each character in the word
7 // Calculate the index for the child node based on current character
8 int index = ch - 'a';
9
10 // If the child node does not exist, create a new one
11 if (!node->children[index]) {
12 node->children[index] = new Trie();
13 }
14
15 // Move to the child node
16 node = node->children[index];
17
18 // Add the index of the word to the current node's vector (only if size is < 3)
19 if (node->indices.size() < 3) {
20 node->indices.push_back(wordIndex);
21 }
22 }
23 }
24
25 // Function to search prefixes in the Trie and return the indices of words
26 vector<vector<int>> Search(string &prefix) {
27 Trie* node = this; // Start from the root node
28 int prefixLength = prefix.size();
29 vector<vector<int>> results(prefixLength); // Initialize results based on prefix length
30
31 for (int i = 0; i < prefixLength; ++i) {
32 // Calculate the index for the next character
33 int index = prefix[i] - 'a';
34 // If there isn't a child node with the next character, exit loop
35 if (!node->children[index]) {
36 break;
37 }
38 // Move to the next node
39 node = node->children[index];
40 // Use move semantic to efficiently pass the vector of indices
41 results[i] = move(node->indices);
42 }
43 return results;
44 }
45
46private:
47 // Vector to store pointers to child Trie nodes, one for each letter a-z
48 vector<Trie*> children = vector<Trie*>(26);
49 // Vector to store indices of inserted words
50 vector<int> indices;
51};
52
53class Solution {
54public:
55 // Function to get suggested products after each character of searchWord is typed
56 vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
57 // Sort the products lexicographically
58 sort(products.begin(), products.end());
59
60 Trie* trie = new Trie();
61 // Insert all products into the Trie
62 for (int i = 0; i < products.size(); ++i) {
63 trie->Insert(products[i], i);
64 }
65
66 vector<vector<string>> suggestions; // Final result of suggested products
67 // Get the list of product indices for each prefix of the searchWord
68 for (auto &indices : trie->Search(searchWord)) {
69 vector<string> temp;
70 // Build a list of product strings to suggest based on the indices
71 for (int idx : indices) {
72 temp.push_back(products[idx]);
73 }
74 // Add the list of products to suggestions using move semantics
75 suggestions.push_back(move(temp));
76 }
77 return suggestions;
78 }
79};
80
1// Represents a Trie node
2interface TrieNode {
3 children: Array<TrieNode | null>;
4 indices: number[];
5}
6
7// Initializes a Trie node with 26 possible children (a to z)
8const createTrieNode = (): TrieNode => ({
9 children: new Array(26).fill(null),
10 indices: [],
11});
12
13// The Trie data structure, with a root node initialized
14const trieRoot: TrieNode = createTrieNode();
15
16// Inserts a word into the Trie
17function insert(word: string, wordIndex: number): void {
18 let node: TrieNode = trieRoot;
19
20 for (const ch of word) {
21 const index = ch.charCodeAt(0) - 'a'.charCodeAt(0);
22
23 if (!node.children[index]) {
24 node.children[index] = createTrieNode();
25 }
26
27 node = node.children[index] as TrieNode;
28
29 if (node.indices.length < 3) {
30 node.indices.push(wordIndex);
31 }
32 }
33}
34
35// Searches prefixes in the Trie and returns the indices of words
36function search(prefix: string): Array<number[]> {
37 let node: TrieNode = trieRoot;
38 const results: Array<number[]> = [];
39
40 for (let i = 0; i < prefix.length; ++i) {
41 const index = prefix[i].charCodeAt(0) - 'a'.charCodeAt(0);
42 if (!node.children[index]) {
43 break;
44 }
45
46 node = node.children[index] as TrieNode;
47 results.push([...node.indices]); // Using spread to clone the indices
48 }
49
50 return results;
51}
52
53// Suggests products based on each character of searchWord
54function suggestedProducts(products: string[], searchWord: string): string[][] {
55 products.sort();
56
57 // Insert all products into the Trie
58 products.forEach((product, index) => {
59 insert(product, index);
60 });
61
62 const suggestions: string[][] = [];
63 const indicesList = search(searchWord);
64
65 for (const indices of indicesList) {
66 const temp: string[] = [];
67 for (const idx of indices) {
68 temp.push(products[idx]);
69 }
70 suggestions.push(temp);
71 }
72
73 return suggestions;
74}
75
76// Example usage:
77
78// Define products and a search word
79const products = ['mobile', 'mouse', 'moneypot', 'monitor', 'mousepad'];
80const searchWord = 'mouse';
81
82// Get the suggested products
83const productSuggestions = suggestedProducts(products, searchWord);
84
85// Output the suggestions
86console.log(productSuggestions);
87
Time and Space Complexity
Time Complexity:
-
The
Trie
construction (insert
method):- For each word
w
inproducts
, the insertion into the trie takesO(L)
time, whereL
is the length of the word, as it involves iterating over each character of the word. - The insertion is performed for every word in
products
, so if there areN
words, this part takesO(N * L)
time.
- For each word
-
Sorting the
products
list:- Sorting
N
strings with an average lengthL
costsO(N * L * log(N))
because the comparison between strings isO(L)
and there areO(N * log(N))
comparisons in a typical sorting algorithm like Timsort (used in Python).
- Sorting
-
Searching for prefixes in the
trie
(thesearch
method):- For the search word with length
M
, the search collects up to 3 indices for each of itsM
prefixes. The traversal to a node takesO(M)
and we do thisM
times, so the total cost of this step isO(M^2)
.
- For the search word with length
The dominant term is the sorting O(N * L * log(N))
and the second is trie construction O(N * L)
. Therefore, the overall time complexity is O(N * L * log(N))
.
Space Complexity:
-
The trie construction:
- In the worst case, the trie will have as many nodes as there are characters in the product list, each node containing an array of length 26 and a list of integers. If there are
N
words andL
is the maximum length of a word, then the space complexity isO(N * L)
because each word could potentially introduceL
new nodes to the trie.
- In the worst case, the trie will have as many nodes as there are characters in the product list, each node containing an array of length 26 and a list of integers. If there are
-
The sorting of products does not require additional space proportional to the number of products, as it is done in place (Python's sort is in-place for lists).
-
Output list creation:
- The output list will contain
M
lists, whereM
is the length of thesearchWord
. Each of theseM
lists can contain up to 3 product strings in the worst case. As strings are stored by reference, the actual strings are not duplicated; hence this only increases by a constant factor.
- The output list will contain
Hence, the space complexity is dominated by the trie's space, resulting in O(N * L)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.