Problem - Implement Trie

Implement a trie with these operations:

• Trie(): Initialize the trie
• insert(word): Insert a word into the trie
• search(word): Return true if word is in the trie
• startsWith(prefix): Return true if any word starts with prefix

Example:

trie.insert("apple")
trie.search("apple")   // true
trie.search("app")     // false
trie.startsWith("app") // true

Constraints: words and prefixes consist of lowercase letters, length 1-2000, up to $3 \cdot 10^4$ operations total.