Design Add and Search Words Data Structure
Medium · trie
A word dictionary starts out empty and receives a list of operations. operations[i] is either "add" or "search", and words[i] is the string that operation works on.
"add"stores the lowercase wordwords[i]. Adding a word that is already stored changes nothing."search"treatswords[i]as a pattern made of lowercase letters and the wildcard.. Each.stands for exactly one letter, any letter. The search succeeds when at least one stored word has the same length as the pattern and matches it at every position: a letter must be equal, a.accepts anything.
Return a list of booleans holding the result of every "search" operation, in the order they appear. "add" operations add nothing to the list.
Examples
Example 1
Input: operations = ["add", "add", "search", "search", "search", "search"], words = ["bad", "mad", ".ad", "b..", "bad.", "ba"]
Output: [true, true, false, false]
".ad" matches "bad" and "mad", and "b.." matches "bad". The pattern "bad." needs a word of length 4 and "ba" needs a word of length 2, and no stored word has either length.
Example 2
Input: operations = ["search", "add", "search", "search"], words = ["a", "a", "a", "."]
Output: [false, true, true]
Nothing is stored for the first search. After "a" is added, both "a" and "." match it.
Example 3
Input: operations = ["add", "add", "search", "search", "search"], words = ["tea", "ten", "to.", "t.n", ".e."]
Output: [false, true, true]
"to." fails because the second letter of both words is "e". "t.n" matches "ten" and ".e." matches either word.
Constraints
- 1 <= len(operations) <= 10^4
- len(words) == len(operations)
- operations[i] is one of add, search
- 1 <= len(words[i]) <= 20
- A word to add contains lowercase English letters only
- A search pattern contains lowercase English letters and '.', with at most 2 occurrences of '.'