Design Add and Search Words Data Structure

Problem

Build a structure that stores lowercase words and answers pattern queries. It supports:

• addWord(word): store word.

• search(pattern): return True if some stored word matches pattern, where each . in the pattern matches exactly one arbitrary letter and every other character must match literally. The lengths must be equal.

• Words and patterns are each at most a few dozen characters long.

• Words contain only a–z; patterns contain a–z and ..

• Expect up to several thousand search calls, most patterns holding only one or two dots (the solution must still be correct if a pattern is nothing but dots).

Examples

• addWord("fox"), addWord("box"), addWord("fix"); search("cox") → False (no word starts with c); search("fox") → True; search(".ox") → True because the dot can stand for f or b; search("f.x") → True.
• addWord("go"); search(".") → False because lengths differ; search("..") → True.
• addWord("tree"); search("tre") → False: a prefix is not a match, only a full word is.

Hints

1. Without dots, this is exactly a trie with insert and search.
2. When you meet a ., you cannot pick a single child. What do you have to do with all of them?
3. Recursive DFS over the trie: on a letter follow one child, on a dot try every child, and succeed only if some branch reaches a terminal node at exactly the last character.