163. Implement Trie (Prefix Tree)
A trie (pronounced "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a set of strings. Implement the Trie class: Trie() initializes the object; insert(word) inserts the string word into the trie; search(word) returns true if word is in the trie (was inserted earlier), and false otherwise; startsWith(prefix) returns true if there is a previously inserted string that has the given prefix, and false otherwise.
Examples
Input: ["Trie","insert","search","search","startsWith","insert","search"] [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output: [null,null,true,false,true,null,true]
Explanation: After inserting 'apple', 'app' is a prefix but not a stored word; inserting 'app' then makes search('app') true.
Constraints
- 1 <= word.length, prefix.length <= 2000; word and prefix consist only of lowercase English letters; at most 3 * 10^4 calls in total to insert, search, and startsWith
Run checks all cases above. Submit evaluates all test cases.