Implement Trie (LeetCode 208)

Implement a prefix tree with insert, exact-word lookup, and prefix lookup operations. Examples Example 1: Input: ["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"] Output: [null, null, true, false, true, null, true] Explanation: PrefixTree prefixTree = new PrefixTree(); prefixTree.insert("dog"); prefixTree.search("dog"); // return true prefixTree.search("do"); // return false prefixTree.startsWith("do"); // return true prefixTree.insert("do"); prefixTree.search("do"); // return true Constraints 1 <= word.length, prefix.length <= 1000 word and prefix are made up of lowercase English letters.