Tries Prefix trees

423. Design Add and Search Words Data Structure

Design a dictionary of words that can find words matching a pattern. Write a class WordDictionary with two methods:

addWord(word) adds word to the dictionary.
search(pattern) returns true if some added word matches pattern, and false otherwise.

A pattern is made of lowercase letters and at most one dot, .. A word matches a pattern when both have the same length and every letter of the pattern equals the letter of the word at the same position. The dot stands for any single letter. So "c.t" matches "cat" and "cut", but not "ct" or "cart".

Your class is tested by replaying a list of calls on a new, empty WordDictionary. ops[i] names the i-th call, "addWord" or "search", and words[i] is the word or pattern it is called with. The answer is the list of every value that search returns, in the order of the calls.

In C# and Go the methods are AddWord and Search, and in Rust addWord is add_word. Go creates the dictionary with Constructor(), and Rust with WordDictionary::new(). The names in ops are the same in every language.

Example 1

Input: ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["cat", "cart", "ca.", "c.rt", "ca", "cat."]

Output: [true,true,false,false]

Explanation: "ca." matches "cat", and "c.rt" matches "cart". "ca" is only the start of the added words, and "cat." needs a word of four letters that starts with "cat", which "cart" does not.

Example 2

Input: ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["dig", "dog", ".og", "d.", "d.g", "do."]

Output: [true,false,true,true]

Explanation: The dot can stand at any position, the first one included. "d." has two letters, and no added word does.

Example 3

Input: ops = ["search", "addWord", "search", "search", "addWord", "search"] words = [".", "a", ".", "a", "b", "."]

Output: [false,true,true,true]

Explanation: The first search finds an empty dictionary. After that, "." matches any word of one letter.

Check your understanding

Work out the answer for this input before you write any code.

ops = ["addWord", "addWord", "search", "search", "search"] words = ["bat", "bun", "b.n", "b.", "bu."]

Constraints

1 ≤ ops.length ≤ 10⁵
Each ops[i] is "addWord" or "search".
words.length equals ops.length.
1 ≤ words[i].length ≤ 100
The words in words have at most 10⁶ letters and dots in all.
A word passed to addWord is made of lowercase English letters.
A pattern passed to search is made of lowercase English letters and at most one ..

Clarifying questions

What you would ask an interviewer before writing any code.