TrieDesignString
Implement a trie that supports three operations: insert w adds a word, search w reports whether exactly that word was inserted before, and startsWith p reports whether any inserted word begins with p. You are given a list of operations to run.
Input
Line 1: q, the number of operations. Next q lines: insert w, search w or startsWith p (lowercase letters).
Output
For every search and startsWith print true or false, one per line, in order.
Constraints
1 <= q <= 10^4 1 <= length of each word <= 20
Example 1
Input
6 insert apple search apple search app startsWith app insert app search app
Output
true false true true
app is only a prefix at first, and a real word after it is inserted.