Implement Trie (Prefix Tree)

Design a data structure that implements a Trie (Prefix Tree).

Implement the Trie class:

• Trie() - initializes the trie.
• insert(word) - inserts the string word into the trie.
• search(word) - returns True if the string word is in the trie (i.e., was previously inserted), and False otherwise.
• startsWith(prefix) - returns True if there is any word in the trie that starts with the given prefix, and False otherwise.

---

Example

Input: ["Trie","insert","search","search","startsWith","insert","search"]
        [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, True, False, True, null, True]
Explanation: After inserting "apple", search("app") is False (not inserted) but startsWith("app") is True. After inserting "app", search("app") becomes True.

---

Constraints

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 10^4 calls will be made to insert, search, and startsWith.