Search Suggestions System

1. Define the problem

You are given a list of products and a searchWord . Imagine someone typing that search word one letter at a time. After each letter, show up to three suggested products that start with what has been typed so far. When more than three products match, show the three that come first in dictionary order. Return one list of suggestions per letter typed. Sort the products once, then insert them into a trie. As each product is inserted, drop its name into every node along its path, but keep at most three names per node. When the typing walk reaches a node, its stored list is already the answer. Because the products were inserted in sorted order, the first three that reach a node are exactly the three smallest in dictionary order.

Constraints

1 ≤ products.length ≤ 1000
1 ≤ products_i.length ≤ 3000
1 ≤ searchWord.length ≤ 1000
All strings consist of lowercase English letters

Example

Inputproducts = ["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 then "mo", five products still match and the three smallest in dictionary order are mobile, moneypot and monitor. From "mou" onwards only mouse and mousepad match, so both are shown.

2. Know the words first

In plain terms

Dictionary order: The order words appear in a dictionary: compare letter by letter, and the first difference decides.
Trie node cache: A small list kept on each trie node holding the best few answers for that prefix, so a lookup needs no searching.
Prefix: The part of the search word typed so far, such as "m", then "mo", then "mou".

3. Visualize the solution

Walking "mouse" letter by letter and reading each node's cached list

m—

o—

u—

s—

e—

Statusinit

Sort the products first, then insert them so every node keeps the best three.

What happens in this step

sorted = mobile, moneypot, monitor, mouse, mousepad
result = [], node = root

Sorting once up front is what makes "the first three to arrive" also mean "the three smallest".

Step 1 of 7

Steps to visualize

The row of cells is the search word, one cell per letter typed.
The value is how many suggestions the trie node for that prefix is holding, capped at three.
The frame covers the prefix typed so far, which is the path walked from the root.
No searching happens at lookup time — the lists were filled in while the sorted products were inserted.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walking "mouse" letter by letter and reading each node's cached list

m—

o—

u—

s—

e—

Statusinit

Sort the products first, then insert them so every node keeps the best three.

What happens in this step

sorted = mobile, moneypot, monitor, mouse, mousepad
result = [], node = root

Sorting once up front is what makes "the first three to arrive" also mean "the three smallest".

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function suggestedProducts(products, searchWord) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.words = [];
    }
  }

  const root = new TrieNode();
  const sorted = [...products].sort();

  for (const product of sorted) {
    let node = root;
    for (const ch of product) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
      if (node.words.length < 3) {
        node.words.push(product);
      }
    }
  }

  const result = [];
  let node = root;

  for (const ch of searchWord) {
    node = node ? node.children[ch] : null;
    result.push(node ? node.words : []);
  }

  return result;
}

Time: O(n log n + total letters across all products)
Space: O(total letters across all products)

6. Test cases

Test cases

Input	Expected	Covers
`products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"], searchWord = "mouse"`	`[["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"]]`	example from the docstring
`products = ["havana"], searchWord = "havana"`	`six lists, each containing only "havana"`	one product matching every prefix
`products = ["bags", "baggage", "banner", "box", "cloths"], searchWord = "bags"`	`[["baggage","bags","banner"], ["baggage","bags","banner"], ["baggage","bags"], ["bags"]]`	the suggestion list shrinks as more letters are typed
`products = ["apple"], searchWord = "z"`	`[[]]`	nothing matches the very first letter typed
`products = ["ab"], searchWord = "abc"`	`[["ab"], ["ab"], []]`	typing past the end of every product gives empty lists from then on
`products = ["aa", "ab", "ac", "ad", "ae"], searchWord = "a"`	`[["aa","ab","ac"]]`	five products match but only three are shown

Search Suggestions System