Implement Trie Prefix Tree
Implement Trie with insert(word), search(word) and startsWith(prefix). search requires a whole inserted word; startsWith requires some inserted word beginning with that prefix.
Example 1
arg 1 = ["Trie","insert","search","search","startsWith","insert","search"]
arg 2 = [[],["camp"],["camp"],["cam"],["cam"],["cam"],["cam"]][null,null,true,false,true,null,true]Explanation
cam is a prefix of camp but not a word until cam itself is inserted.
Example 2
arg 1 = ["Trie","search","startsWith","insert","search"]
arg 2 = [[],["x"],["x"],["x"],["x"]][null,false,false,null,true]Explanation
An empty trie has neither x nor its prefix; insertion changes search(x) to true.
Example 3
arg 1 = ["Trie","insert","insert","search","search","startsWith","insert","search"]
arg 2 = [[],["a"],["a"],["a"],["ab"],["a"],["ab"],["ab"]][null,null,null,true,false,true,null,true]Explanation
Reinserting a changes nothing; ab becomes a full word only after its own insertion.
Constraints
- At most 30000 operations
- Words and prefixes have 1..2000 lowercase English letters
Class contract
TrieArguments: json, jsonSolutionRuns on your device
Loading draft…
Run: 3 examples; Submit: 35 cases, on your device.
["Trie","insert","search","search","startsWith","insert","search"][[],["camp"],["camp"],["cam"],["cam"],["cam"],["cam"]]