1268. Search Suggestions System

MediumTrieArrayStringBinary SearchSortingHeap (Priority Queue)
Leetcode Link

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.

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

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

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

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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:

  1. 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) and v (a list that will store indices of products up to three for the nodes relevant to the search).
    • The children array is initialized with None, indicating that initially, there are no child nodes.

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

  3. Searching the Trie:

    • The search method is used to retrieve the list of product indices as per the characters of the searchWord.
    • 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 to ans.

  4. Constructing the Output:

    • The Solution class has a method called suggestedProducts, 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.

  5. 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 trie search, retrieves the product string from the sorted products list.
    • The outer list comprehension is what generates the list of lists of product names, corresponding to each character of searchWord.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example 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"]
  1. 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.

  1. 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].

  2. 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 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity:

  1. The Trie construction (insert method):

    • For each word w in products, the insertion into the trie takes O(L) time, where L 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 are N words, this part takes O(N * L) time.

  2. Sorting the products list:

    • Sorting N strings with an average length L costs O(N * L * log(N)) because the comparison between strings is O(L) and there are O(N * log(N)) comparisons in a typical sorting algorithm like Timsort (used in Python).

  3. Searching for prefixes in the trie (the search method):

    • For the search word with length M, the search collects up to 3 indices for each of its M prefixes. The traversal to a node takes O(M) and we do this M times, so the total cost of this step is O(M^2).

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:

  1. 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 and L is the maximum length of a word, then the space complexity is O(N * L) because each word could potentially introduce L new nodes to the trie.

  2. 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).

  3. Output list creation:

    • The output list will contain M lists, where M is the length of the searchWord. Each of these M 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.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Trie Introduction

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

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

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 Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ