Implement a Trie class with insert(word), search(word), which returns whether the exact word was inserted, and startsWith(prefix), which returns whether any inserted word starts with the prefix. Words are lowercase letters. The expected output lists the results of the search and startsWith calls.
Before you code
What does reaching a node during a walk prove, and what extra fact distinguishes search from startsWith?
Hints
- Each node holds a map from character to child and a flag marking the end of a word.
- Insert walks from the root, creating missing children, and sets the flag on the last node.
- Write one helper that walks a string and returns the final node or None. search checks the flag on that node; startsWith only checks that it exists.
Production & complexity notes
When solving Implement a trie on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Tries to reinforce the underlying pattern.
What it practices
The basic trie operations, from Tries.