Implement Trie (Prefix Tree)

Problem

Design a data structure that stores a collection of lowercase words and supports three operations:

• insert(word): add word to the structure.
• search(word): return True if exactly this word was previously inserted.
• startsWith(prefix): return True if at least one inserted word begins with prefix.

The same word may be inserted more than once; that should not change the answers.

• Each inserted word or queried prefix is 1 to a few thousand characters long.
• All strings consist of the letters a–z only.
• The structure should stay fast even under tens of thousands of combined calls.

Examples

• insert("banana"), search("banana") → True; search("ban") → False because "ban" was never inserted as a whole word; startsWith("ban") → True because "banana" starts with it.
• After the above, insert("ban"), then search("ban") → True. Marking the node at the end of "ban" as terminal is what flips the answer.
• startsWith("cat") → False on a structure that only holds "banana" and "ban": the root has no child for c.

Hints

1. Storing words in a hash set makes search trivial, but how would you answer startsWith without scanning every stored word?
2. Words that share a prefix should share the storage for that prefix. Think of a tree where each edge is one character.
3. Build a tree of nodes, each holding a map from character to child node plus a boolean "a word ends here" flag. Walk the tree character by character for all three operations.