A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class:
- `Trie()` Initializes the trie object.
- `void insert(String word)` Inserts the string word into the trie.
- `boolean search(String word)` Returns true if the string word is in the trie.
- `boolean startsWith(String prefix)` Returns true if there is a previously inserted string that has the prefix.
checklist Constraints
1 <= word.length, prefix.length <= 2000 word and prefix consist only of lowercase English letters. At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.