Trie Autocomplete
Hard · Classes
A trie (prefix tree) stores words letter by letter. Each node has a dict of children (letter -> node) and a flag that marks the end of a word. Words with the same prefix share the same path, so finding everything that starts with "ca" means walking c, a, then collecting all words below that node.
Complete the Trie class:
- insert(word): add a word (inserting the same word twice changes nothing)
- autocomplete(prefix): return all inserted words that start with prefix, sorted alphabetically; an empty prefix returns every word, and no match returns []
The driver run_trie is already written.