LeetCode 208 ·
Medium
Implement Trie (Prefix Tree)
Implement a trie supporting insert, search, and startsWith.
Try it
Step through the core mechanic. The simulator below runs the trie shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Trie — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
Each node holds child links (26 or a map) and an end-of-word flag. insert/search walk character by character; search needs the end flag, startsWith only needs the path to exist.
| Aspect | Value |
|---|---|
| Pattern | Trie |
| Recognise it by | Prefix-keyed insert/search/startsWith. |
| Time complexity | O(L) |
| Space complexity | O(Σ·L) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.