Implement Trie (Prefix Tree)
Part of Practice: Build & Search Tries
Build a trie (pronounced "try", also called a prefix tree) — a tree that stores strings so that words sharing a prefix share a path. Implement three operations:
insert(word): store a word.search(word): return true only if this exact word was inserted before.startsWith(prefix): return true if any inserted word begins with this prefix.
All strings are lowercase English letters, each up to 2000 characters, and there can be up to 30,000 total calls, so every operation should cost time proportional to the length of its input string — not the number of stored words.
Examples
- Input:
- insert("apple"), search("apple"), search("app"), startsWith("app")
- Output:
- null, true, false, true
"apple" was inserted, so searching it succeeds. "app" was never inserted as a full word, so search fails — but it is a prefix of "apple", so startsWith succeeds.
- Input:
- insert("apple"), insert("app"), search("app")
- Output:
- null, null, true
After "app" is inserted as its own word, the node at the end of a-p-p gets its end-of-word flag set, so searching "app" now returns true.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.