Autocomplete over a dictionary of words by prefix. Best structure?
Options
- A hash set of all the words
- A trie (prefix tree) (Correct option)
- A min-heap ordered by word length
- A linked list of the words in order
Answer
Trie (prefix tree)
Why
A trie is a tree where each edge is a letter. Words with the same beginning share the same path: 'car', 'cart' and 'care' all go through c → a → r.
To autocomplete 'ca', walk 2 steps down and collect all words below that node.
Lookup time depends on the prefix length, not on how many words are stored.
Remember
Prefix search → trie.