Problem. Implement a structure with:
addWord(word): store a lowercase word;search(pattern): return True if any stored word matches, where.matches any one letter.
addWord("bad"), addWord("dad"), addWord("mad")
search("pad") → False
search("bad") → True
search(".ad") → True
search("b..") → True
search("b...") → False (no 4-letter word)
A trie handles exact letters by following one edge. A dot means "any edge": the walk branches into every existing child. That turns the walk into a depth-first search over the trie, but one that only explores paths that actually exist.
ML context. OCR and speech systems often know most characters of a word but not all: "c?t" where one letter was unreadable. Recovering the candidates is exactly this search, and ranking them by word frequency (or by a language model) picks the likely one (Change D). The same pattern lookup filters a vocabulary by shape, such as all 5-letter tokens ending in "ing".