Implement Trie
Implement Trie is a medium Tries problem from the Blind 75. The key pattern is prefix tree, and a good solution runs in O(L) per operation time.
Problem
Process insert, search, and startsWith operations on lowercase words; output results for query operations.
Examples
Example 1
Input
[["insert","codex"],["search","code"],["startsWith","code"],["search","codex"]]Output
[false,true,true]Example 2
Input
[["insert","piano"],["search","piano"],["search","pian"],["startsWith","pian"],["insert","pian"],["search","pian"]]Output
[true,false,true,true]Example 3
Input
[["startsWith","a"]]Output
[false]Approach
Each node holds child links and an end-of-word flag. Insert, search and prefix checks all walk one node per character.
| Pattern | Prefix tree |
|---|---|
| Time | O(L) per operation |
| Space | O(total characters) |
Watch out for
search needs the end-of-word flag; startsWith only needs the path to exist.