Implement a Trie (Prefix Tree)
Medium · Trie · about 20 minutes
Asked at Google, Amazon, Microsoft, Uber.
Implement a Trie with insert(word), search(word) (true if the exact word was inserted) and startsWith(prefix) (true if any inserted word starts with the prefix). Words use lowercase letters.