Design Add and Search Words

Store words and support . as a wildcard that matches any one character.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Design Add and Search Words: A literal follows one child; a dot recursively tries each child until one full-length terminal path succeeds.

Input and goalStore words and support `.` as a wildcard that matches any one character.

Store three terminal pathsbat, dad, and mad share root but have separate first-letter branches.

double border complete word

wordsbat,dad,madquery.adterminalbat,dad,mad

Recognize it

A stored-prefix query contains a symbol matching any one character.

Keep true

match(index,node) is true exactly when a terminal descendant matches the remaining suffix.

Reuse it

Branch recursion only at ambiguous symbols and preserve terminal semantics at exact query length.

Pattern: Trie plus DFS when a wildcard appears.

Simple idea: Normal letters follow one child. A dot tries every child. The end marker still checks that the full word length matched.

class WordDictionary:
   def __init__(self) -> None:
      self.root: dict = {}

   def add_word(self, word: str) -> None:
      node = self.root
      for char in word:
         node = node.setdefault(char, {})
      node[None] = True

   def search(self, word: str) -> bool:
      def match(index: int, node: dict) -> bool:
         if index == len(word):
            return None in node
         if word[index] == ".":
            return any(match(index + 1, child) for key, child in node.items() if key)
         return word[index] in node and match(index + 1, node[word[index]])

      return match(0, self.root)

Cost: Adding takes $O(L)$ time. A normal search takes $O(L)$. Many wildcards can make search exponential in the word length.