Implement Trie

A trie (also called a prefix tree) stores words letter by letter: every node stands for one letter, and words that begin the same way share one path down from the root. That makes two questions fast to answer, which is why autocomplete and spell checkers use it: was this exact word stored, and does any stored word begin with this prefix?

Implement the Trie class:

• Trie() creates an empty trie.
• insert(word) stores the string word.
• search(word) returns true if word itself was stored earlier, and false otherwise.
• startsWith(prefix) returns true if at least one stored word begins with prefix, and false otherwise.

Each example lists the calls in order, then each call's arguments, then each call's result (null for the constructor and for insert, which returns nothing).

---

Examples

Example 1

Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["plant"], ["plant"], ["plan"], ["plan"], ["plan"], ["plan"]]
Output: [null, null, true, false, true, null, true]

With only "plant" stored, search("plan") is false: "plan" is a prefix of a stored word, not a stored word, so startsWith("plan") is true. Once "plan" is inserted as well, search("plan") becomes true.

---

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 10⁴ calls in total will be made to insert, search, and startsWith.