Trie
https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58832
Summary
Application
- Autocomplete
- Spell Checker
- IP routing Longest Prefix Mathcing
- T9 predictive text
- Solving word game
Compare with HashTable and BST
HashTable
O(1) time complexity for looking a key.
But not efficient in operations like:
- Finding all keys with a common prefix
- Enumerating a dataset of strings in lexicographical order
Also,
HashTable increase in size (hash collision)when storing many keys with the same prefix.
Trie
Use less space compared to Hash Table