Design Add and Search Words Data Structure

A crossword helper keeps a growing list of words. Players ask whether some stored word fits a partly filled row, where unknown squares are written as ..

Build WordStore:

• WordStore() starts empty.
• add(word) -> None stores word. Adding a word that's already stored changes nothing.
• matches(pattern) -> bool returns True if some stored word has exactly the pattern's length and agrees with it at every position, where each . stands for any single letter.

ws = WordStore()
ws.add("lamp")
ws.add("limp")
ws.add("lampshade")
ws.matches("l.mp")     # True   ("lamp" and "limp")
ws.matches("lam")      # False  (a prefix of a word isn't a word)
ws.matches("....")     # True
ws.matches(".....")    # False  (no stored word has 5 letters)
ws.matches("lamp.")    # False
ws.matches("la.pshade")   # True

Constraints: words and patterns have length 1 to 20; words use a-z, and patterns use a-z and . (at most 3 dots each). There are up to 2 * 10^4 words and 10^4 lookups.

Comparing a pattern against every stored word is too slow here. add should cost O(length of the word), a lookup without dots O(length of the pattern), and a lookup with dots should only explore letters that stored words actually use at those positions.