Implement Trie (Prefix Tree)
Support insert, exact word search, and prefix search.
Why does this pattern fit?
Restate the exact job
Support insert, exact word search, and prefix search.
Each character is one edge; word completion is separate from path existence.
O(L) per operation · O(total characters) space
Treating every prefix node as a complete word breaks exact search.
How to solve Implement Trie (Prefix Tree)
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Support insert, exact word search, and prefix search.
Why Tries & prefix search fits
Each character is one edge; word completion is separate from path existence.
State to maintain
Trie nodes with child maps and an end-of-word flag.
Transition
Walk or create edges on insert; searches walk edges and check the appropriate terminal condition.
Time and space
O(L) per operation · O(total characters) space
Counterexample to the tempting mistake
Treating every prefix node as a complete word breaks exact search.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.