Store words in a trie and search patterns where a dot matches any letter, branching into every child only when you meet a dot.
▼The problem
LeetCode 211, Design Add and Search Words Data Structure (Medium). Build a WordDictionary with addWord(word) and search(word), where the search pattern may contain dots and a dot matches any one letter.
Example (from the problem statement): add bad, dad, mad. Then search("pad") → False (no p under the root), search("bad") → True, search(".ad") → True (the dot can be b; DFS tries b first and stops there), search("b..") → True (each dot has exactly one child to try: a, then d).
The solution
class Node:
def __init__(self): self.kids, self.end = {}, False
class WordDictionary:
def __init__(self): self.root = Node()
def addWord(self, word):
node = self.root
for ch in word:
node = node.kids.setdefault(ch, Node())
node.end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.end
if word[i] == '.':
return any(dfs(k, i + 1) for k in node.kids.values())
kid = node.kids.get(word[i])
return kid is not None and dfs(kid, i + 1)
return dfs(self.root, 0)Transcript
Add and Search Words. Design a dictionary that can add words and search for them, where a dot in the search matches any letter.
Add bad, dad and mad. Search pad: false. Bad: true. Dot A D: true. B dot dot: true.
The simple way keeps a list and checks the pattern against every word. Each search scans them all.
A trie does better. Each lantern holds one letter, and each word is a path down from the root. A candle marks where a word ends. A letter follows one string down. A dot shines into every child, and depth-first search tries each branch until one finds a candle.
Add walks down, creating missing children, then marks the end. Search recurses with a node and a position. At the pattern's end, return the mark. A dot tries every child and succeeds if any does. A letter follows its child, or fails if there's none.
Let's light it up. Bad, dad and mad hang from the root on separate strings. Search pad: no P under the root, false. Bad: B, A, D, a candle. True. Dot A D: the dot shines into B, D and M. B's branch finds a candle first: true. B dot dot: each dot has one child to try. True.
Adding takes one step per letter. A search without dots does too. But each dot can branch twenty-six ways, so with d dots, the worst case is twenty-six to the d, times the length.
Follow the letters, branch on the dots. That's Add and Search Words.