Trie: Add and Search Words
Problem statement
Build a trie (prefix tree) that stores words, and run a list of operations on it. The trie starts empty. Each string in operations is one of:
"add word": storeword. The result istrueifwordwas not stored before, andfalseif it was already stored."search word": the result istrueifworditself has been added."prefix p": the result istrueif at least one added word starts withp. A word counts as a prefix of itself.
Return one boolean per operation, in order.
Function
runTrie(operations: String[]) → boolean[]Examples
Example 1
operations = ["add apple","search apple","search app","prefix app","add app","search app"]return = [true,true,false,true,true,true]apple is new, so the first result is true, and searching for it is true. app has not been added yet, so search app is false, but apple starts with app, so prefix app is true. After add app (new, true), search app is true.
Example 2
operations = ["add cat","add cat","prefix cats","prefix c"]return = [true,false,false,true]The second add cat returns false because cat is already stored. No stored word starts with cats, while cat starts with c.
Example 3
operations = ["search a","prefix a","add a","prefix a"]return = [false,false,true,true]The trie is empty at first, so both queries are false. After adding a, the prefix a matches the word a itself.
Constraints
1 <= operations.length <= 2 * 10^4- Each operation is
"add w","search w", or"prefix w", with exactly one space. - Each
whas 1 to 50 lowercase English letters.