Trie
A tree with one node per character, so every path from the root spells a prefix and words share their common prefixes.
Trie: Insert words sharing prefixes
"cart", letter 'c'. The current node already has a child 'c', shared with an earlier word, so follow it.
Cost
- Insert
- O(L)
- Search
- O(L)
- Prefix query
- O(L + results)
- Space
- O(total characters * alphabet)
L is the word length.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Trie covers these too, in the same run.