46 / 75
Medium
Implement Trie (Prefix Tree)
#46triedesignstringhash-table
Build tree where each node has 26 children (a-z) and boolean flag for word endings.
Example:
Input:
['Trie','insert','search','search','startsWith'], [[],['apple'],['apple'],['app'],['app']]Output:
[null,null,true,false,true]Common Mistakes:
- Not marking word endings (all prefixes would match search)
- Forgetting to create new nodes when inserting
- Using HashMap instead of array (slower for this use case)
- Confusing search (exact match) with startsWith (prefix match)
Notes:
Foundation for autocomplete, spell check, IP routing. Insert/Search/StartsWith: Time O(m) where m=word length, Space O(alphabet_size * n * m) worst case.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Build tree where each node has 26 children (a-z) and boolean flag for word endings.
Example:
Input:
['Trie','insert','search','search','startsWith'], [[],['apple'],['apple'],['app'],['app']]Output:
[null,null,true,false,true]Common Mistakes:
- Not marking word endings (all prefixes would match search)
- Forgetting to create new nodes when inserting
- Using HashMap instead of array (slower for this use case)
- Confusing search (exact match) with startsWith (prefix match)
Notes:
Foundation for autocomplete, spell check, IP routing. Insert/Search/StartsWith: Time O(m) where m=word length, Space O(alphabet_size * n * m) worst case.
46/75
Implement Trie (Prefix Tree)