Typeahead Top Three
Problem
A shop has a list of distinct lowercase product names. A customer types a search word one character at a time. After each character, suggest up to three product names that start with everything typed so far, choosing the alphabetically smallest ones. Return one list of suggestions per typed character.
Examples
Input: products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"], word = "mouse"
Output: [["mobile", "moneypot", "monitor"],
["mobile", "moneypot", "monitor"],
["mouse", "mousepad"],
["mouse", "mousepad"],
["mouse", "mousepad"]]Input: products = ["bag", "bags", "banner", "box"], word = "bax"
Output: [["bag", "bags", "banner"], ["bag", "bags", "banner"], []]
Why: once no product matches, it stays that way for longer prefixesInput: products = ["bag"], word = "cat"
Output: [[], [], []]
Why: edge case, not even the first character matchesHints
0 / 3
Filtering the whole product list again after every keystroke repeats the same comparisons. Each new prefix only narrows the previous one.
In a trie, every prefix is a single node, and the products starting with that prefix are exactly the words below it. If each node already knew its best three, a keystroke would be one step down the tree.
Sort the products, then insert them in that order. On the way down each path, append the product to the node's suggestion list if it holds fewer than three, so every list ends up with the three smallest. To answer, walk down one character per keystroke, recording each node's list, and record empty lists once the walk falls off the tree.
Solution
Inserting the products in sorted order means the first three words to pass through any node are the three smallest with that prefix, so each node can keep a short suggestion list filled during insertion and never touched again. Answering is then one step down the tree per typed character, reading the list stored there. Once a character has no child, no longer prefix can match either, so the walk records empty lists from then on. Sorting costs O(n log n) comparisons, building costs O(total characters), and each keystroke is O(1) plus copying at most three names.
def suggestions(products, word):
root = {}
for p in sorted(products): # sorted, so the first three are the smallest
node = root
for ch in p:
node = node.setdefault(ch, {"#": []})
if len(node["#"]) < 3:
node["#"].append(p) # each node remembers its top three
out, node = [], root
for ch in word:
node = node.get(ch) if node else None # once off the tree, stay off
out.append(node["#"] if node else [])
return out
print(suggestions(["mobile", "mouse", "moneypot", "monitor", "mousepad"], "mouse")[2])
# -> ['mouse', 'mousepad']
print(suggestions(["bag", "bags", "banner", "box"], "bax"))
# -> [['bag', 'bags', 'banner'], ['bag', 'bags', 'banner'], []]
print(suggestions(["bag"], "cat")) # -> [[], [], []]Stuck on the idea rather than the code? Prefix Search covers it.