Implement Trie (Prefix Tree)
Medium · trie
A collection of lowercase words starts out empty and receives a list of operations. operations[i] is one of "insert", "search" or "starts_with", and words[i] is the string that operation works on.
"insert"addswords[i]to the collection. Adding a word that is already there changes nothing."search"asks whetherwords[i]is exactly one of the words added so far."starts_with"asks whether at least one word added so far begins withwords[i]. A word begins with itself, so a stored word always counts as a match for itself.
Return a list of booleans holding the answer to every "search" and "starts_with" operation, in the order they appear. "insert" operations add nothing to the list.
Examples
Example 1
Input: operations = ["insert", "search", "search", "starts_with", "insert", "search"], words = ["apple", "apple", "app", "app", "app", "app"]
Output: [true, false, true, true]
"apple" is stored, so searching for it succeeds. "app" is only a prefix of it, so searching for "app" fails but starts_with "app" succeeds. After "app" is inserted, searching for it succeeds.
Example 2
Input: operations = ["starts_with", "insert", "starts_with", "starts_with", "search"], words = ["a", "cat", "ca", "cats", "ca"]
Output: [false, true, false, false]
Nothing is stored at first. Afterwards "cat" begins with "ca", but nothing begins with "cats", and "ca" is not a stored word.
Example 3
Input: operations = ["insert", "insert", "search", "search", "starts_with"], words = ["go", "gopher", "go", "gop", "gophers"]
Output: [true, false, false]
Both "go" and "gopher" are stored. "gop" is a prefix but not a stored word, and no stored word begins with "gophers".
Constraints
- 1 <= len(operations) <= 10^4
- len(words) == len(operations)
- operations[i] is one of insert, search, starts_with
- 1 <= len(words[i]) <= 20, lowercase English letters only