Design a Trie

Implement a trie (prefix tree) data structure that supports the following operations:

• insert(word): inserts the string word into the trie.
• search(word): returns true if word was previously inserted into the trie (as a complete word), and false otherwise.
• startsWith(prefix): returns true if any word previously inserted into the trie starts with prefix, and false otherwise.

All three operations must run in time proportional to the length of the input string, independent of how many words are stored.

Example 1

trie = Trie()
trie.insert("apple")
trie.search("apple")     # -> true
trie.search("app")       # -> false (only "apple" was inserted)
trie.startsWith("app")   # -> true  ("apple" starts with "app")
trie.insert("app")
trie.search("app")       # -> true  (now "app" is its own word)

Example 2

trie = Trie()
trie.insert("bat")
trie.insert("battery")
trie.startsWith("bat")   # -> true
trie.startsWith("bad")   # -> false
trie.search("batt")      # -> false (prefix only, not inserted as a word)

Constraints

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