180. Wildcard Word Dictionary

Why this mechanism works

Reuse the trie from kata 179. A literal pattern character chooses one edge, while a wildcard must try every child edge. The recursive state needs both the current trie node and the pattern index. Reaching the end of the pattern succeeds only at a terminal node, even after wildcards.

State and boundaries

match(node,i) asks whether some stored suffix below node matches pattern[i:]. The prefix before i has already matched.

Protocol

1. Insert words using the trie.
2. At pattern end return the terminal flag.
3. On a literal follow its child if present.
4. On a dot try every child at index i+1.
5. Succeed if any branch completes.

Visualization

stored bad, dad, mad
pattern .ad -> branch b/d/m -> literal a -> literal d -> terminal
pattern b.  -> ends at nonterminal prefix -> False

Python implementation

from kata_179 import Trie
from structures import run_operations

class WordDictionary:
    def __init__(self):
        self.trie = Trie()

    def addWord(self, word):
        self.trie.insert(word)

    def search(self, pattern):
        def match(node, i):
            if i == len(pattern):
                return node.terminal
            char = pattern[i]
            if char == '.':
                return any(match(child, i + 1) for child in node.children.values())
            child = node.children.get(char)
            return child is not None and match(child, i + 1)
        return match(self.trie.root, 0)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L6 __init__: self.trie = Trie()
self=WordDictionary{'trie':Trie...}

L9 addWord: self.trie.insert(word)
self=WordDictionary{'trie':Trie...}; word='bad'

L9 addWord: self.trie.insert(word)
self=WordDictionary{'trie':Trie...}; word='dad'

L12 search: def match(node, i):
self=WordDictionary{'trie':Trie...}; pattern='.ad'

L13 match: if i == len(pattern):
node=TrieNode{'children':{...:..., ...:...}, 'terminal':False}; i=0; pattern='.ad'

L15 match: char = pattern[i]
node=TrieNode{'children':{...:..., ...:...}, 'terminal':False}; i=0; pattern='.ad'; char='.'

L13 match: if i == len(pattern):
node=TrieNode{'children':{...:...}, 'terminal':False}; i=1; pattern='.ad'

L15 match: char = pattern[i]
node=TrieNode{'children':{...:...}, 'terminal':False}; i=1; pattern='.ad'; char='a'

... 11 intermediate state changes omitted ...

L15 match: char = pattern[i]
node=TrieNode{'children':{...:...}, 'terminal':False}; i=1; pattern='b.'; char='.'

L13 match: if i == len(pattern):
node=TrieNode{'children':{...:...}, 'terminal':False}; i=2; pattern='b.'

L17 <genexpr>: return any(match(child, i + 1) for child in node.children.values())
.0=dict_valueiterator; child=TrieNode{'children':{...:...}, 'terminal':False}; i=1

L17 <genexpr>: return any(match(child, i + 1) for child in node.children.values())
.0=dict_valueiterator; child=TrieNode{'children':{...:...}, 'terminal':False}; i=1

L6 __init__: self.trie = Trie()
self=WordDictionary{'trie':Trie...}

L9 addWord: self.trie.insert(word)
self=WordDictionary{'trie':Trie...}; word=''

L12 search: def match(node, i):
self=WordDictionary{'trie':Trie...}; pattern=''

L13 match: if i == len(pattern):
node=TrieNode{'children':{}, 'terminal':True}; i=0; pattern=''

L12 search: def match(node, i):
self=WordDictionary{'trie':Trie...}; pattern='.'

L13 match: if i == len(pattern):
node=TrieNode{'children':{}, 'terminal':True}; i=0; pattern='.'

L15 match: char = pattern[i]
node=TrieNode{'children':{}, 'terminal':True}; i=0; pattern='.'; char='.'

L17 <genexpr>: return any(match(child, i + 1) for child in node.children.values())
.0=dict_valueiterator; i=0

Why the solution is correct

A literal transition matches precisely its required character. A wildcard transition enumerates all possible one-character matches and no zero- or multi-character matches. The terminal base enforces exact length and word completion. Induction on remaining pattern length proves the search result.

Time and space

Insertion takes expected O(L). Search visits at most O(V) relevant trie nodes; a coarse branching bound is O(b^L) for branching factor b and length L. O(L) recursive depth, plus shared trie storage.

Common mistakes

Returning true merely when the pattern ends accepts prefixes that are not words. Advancing the trie without advancing i makes a dot behave like an unbounded wildcard.

Reasoning card

Transfer exercise

Add '*' meaning any number of characters. Identify the new branching transitions and why memoizing (node,index) becomes useful.