Loading problem…
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.
Example 1
Input: operations = ["Trie","insert","search","search","startsWith","insert","search"], arguments = [[],["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.
Example 2
Input: operations = ["Trie","insert","search","startsWith"], arguments = [[],["hello"],["hello"],["hell"]]
Output: [null,null,true,true]
Explanation: "hello" was inserted, so search("hello") is true, and "hell" is a prefix of it, so startsWith("hell") is also true.
Example 3
Input: operations = ["Trie","search","startsWith"], arguments = [[],["a"],["a"]]
Output: [null,false,false]
Explanation: Nothing inserted yet, so both queries fail.
Store the words as overlapping paths in a tree, one edge per character. Every node is a map from a character to a child node, and a node flagged as a word-end marks that the path taken to reach it spells a complete inserted word. Because shared prefixes share the same nodes, `search` and `startsWith` are just walks down the tree that cost only as much as the query's length — independent of how many words are stored.
Run checks all cases above. Submit evaluates all test cases.