188. Implement Trie (Prefix Tree)
A trie (prefix tree) stores a set of strings as a tree of characters: every path down from the root spells a prefix, and words that share a beginning share those tree nodes. It is the structure behind autocomplete and spell-check.
Build a Trie class with three methods: insert(word) adds word to the set, search(word) returns true only if that exact word was inserted before, and starts_with(prefix) (startsWith in C++/Java) returns true if any inserted word begins with prefix.
Your class is driven by a scripted list of operations read from input. For every search and startsWith call, print the boolean it returns — true or false, one per line, in call order. All words and prefixes are non-empty and use only lowercase letters a–z.
Example 1:
Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output: [true, false, true, true]
Explanation: After inserting "apple": the exact word "apple" is found, "app" is only a prefix (so search says false but startsWith says true). Once "app" itself is inserted, searching it succeeds.
Example 2:
Input: insert("cat"), startsWith("ca"), startsWith("car"), search("dog")
Output: [true, false, false]
Explanation: "ca" is a prefix of the stored word "cat", but no stored word begins with "car", and "dog" was never inserted.
Constraints:
- 1 ≤ q ≤ 3 * 10⁴ operations in total
- 1 ≤ w.length ≤ 200; w consists of lowercase English letters only
- At least one operation is a search or a prefix query.
- The same word may be inserted more than once; that changes nothing.
Hints:
Storing every word in a hash set makes search trivial — but startsWith then has to scan every stored word. What structure lets shared beginnings share work?
Make each node a map from character to child node. insert walks the word, creating children as needed, and flags the last node as "a word ends here". search and startsWith both walk the same way; they differ only in whether the final node must carry that end-of-word flag.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Expected output: [true, false, true, true]