Search Suggestions System

Medium#1268insert and search

There is a list of products and a word being typed. After each typed letter, suggest up to three products that start with the letters typed so far, the smallest in alphabetical order first. Return one list per letter. Our example: products [ox, on, of, or], typed "oxen" — the answer is [[of, on, or], [ox], [], []].

1268 Search Suggestions SystemWalkthrough · 1×

Example: products [ox, on, of, or], searchWord "oxen". Each node keeps up to 3 suggestions: the row node.top shows them for the current node.

rootproductsnode.top—productsoxonoforresult
in the triejust addedthe path so far; a stored suggestioncurrent node and productmissing letter

Sort the products: [ox, on, of, or] becomes [of, on, or, ox]

01/68
restart · back · play · step
Speed
1function suggestedProducts(products, searchWord):
2 sort products
3 root = new node // node.top: its first 3 words
4 for each word in products:
5 node = root
6 for each ch in word:
7 if ch not in node.children:
8 node.children[ch] = new node
9 node = node.children[ch]
10 if len(node.top) < 3:
11 append word to node.top
12 result = []
13 node = root
14 for each ch in searchWord:
15 if node is not none:
16 node = node.children.get(ch) // or none
17 append (node.top if node else []) to result
18 return result
state
products
[ox, on, of, or]
word
–
ch
–
node
–
node.top
–
result
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every product that starts with a prefix passes through that prefix's node when it is inserted, so the node sees all of its candidates.
  2. The products are inserted in sorted order, so the first 3 that pass through a node are the 3 smallest, and the node can stop taking words once it has 3.
  3. Typing walks one node per letter. Once a letter is missing, no product starts with the typed letters, and none starts with any longer prefix either, so every later list is [].

Complexity

Time O(n log n · L) to sort n products of up to L letters, plus O(total letters) to insert them and O(len(searchWord)) to type: each list is ready in its node. Memory O(total letters): a node per letter with at most 3 words in it.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.