Implement Trie (Prefix Tree)

Medium

Implement a trie with insert(word), search(word) (returns whether the exact word was inserted), and startsWith(prefix) (returns whether any inserted word has the given prefix).

Example 1

Input:  operations = ["Trie","insert","search","search","startsWith","insert","search"], values = [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]

Constraints

• 1 <= word.length, prefix.length <= 2000
• Words consist of lowercase English letters.
• At most 3*10^4 calls.