Design Add and Search Words Data Structure — The Smudged Ledger

Boss 2: The Smudged Ledger

Boss 1's walks were deterministic: each letter named its door, one path, no choices. This boss adds a single character to the query alphabet, the wildcard ., and that one character changes the walk's shape: from a line into a tree of attempts. Recursion, which the trie seemed to have left behind in Dungeon 7, walks right back in.

The story

Hotel fire, water-soaked ledger, and a precinct registry built exactly like the post office wall: names filed letter by letter, flags on the final holes.

Filed so far: bad, dad, mad.

root ── b ── a ── d🚩
    ├── d ── a ── d🚩
    └── m ── a ── d🚩

The witnesses, though:

• "The name was bad." Plain walk: b, a, d, flag. Confirmed.
• "It was .ad, I couldn't see the first letter." First letter unknown: try every first door. b? leads to a-d🚩, match. Confirmed (via bad, and dad and mad would've matched too, one is enough).
• "It was b..." Walk b, then two unknowns: from a (the only door after b), then from d... flag. Confirmed.
• "It was .a" Two letters only. Walks reach a-holes... no flags two letters deep (all names here are three letters). Not confirmed. Length is still length; smudges aren't elastic.

The rule the detective works by: a readable letter follows its one door; a smudge fans out through every door at that position, and each fanned branch continues the rest of the name independently. Any branch reaching the final letter with a flag confirms.

The problem, dressed up properly

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() initializes the object.
• void addWord(word) adds word to the data structure.
• bool search(word) returns true if there is any string in the data structure that matches word, or false otherwise. word may contain dots . where a dot can be matched with any letter.

LeetCode 211. Added words are plain lowercase; only queries carry dots.

The naive attempt

A list of words; on search, compare the query against every stored word, letter by letter, dots matching anything:

def search(self, word):
    return any(
        len(w) == len(word) and all(q == '.' or q == c for q, c in zip(word, w))
        for w in self.words
    )

Correct, trivially. O(n · L) per query, every stored word scanned every time. The trie's whole promise was cost independent of n, and the promise survives the wildcard partially: readable letters still prune to one door, and pruning is the whole game. The naive version can't prune at all.

The weapon: fan out at the dot, walk everywhere else

addWord is Boss 1's insert, unchanged, character for character.

search becomes a recursion over (position in query, node in trie):

• Past the last letter: success exactly if this node carries the flag.
• Readable letter: its door or bust; follow it, recurse on the rest.
• Dot: try every door this node has, recurse on the rest through each, succeed if any branch succeeds.

Notice the fan-out tries the doors the node actually has, not all 26 letters blindly. After b, there's one door (a); a dot there fans out to exactly one branch. The trie's sparseness is the pruning: dead prefixes were never built, so the recursion can't waste time in them. That's what the naive list version fundamentally lacked, its dead ends must be walked to be discovered.

Watching it work

Query .ad against bad/dad/mad:

match(0, root): '.' → fan out over root's doors: b, d, m
├─ b: match(1, b-node): 'a' → door exists → match(2, ba-node): 'd' → door, flag ✓
│                                                    CONFIRMED, short-circuit
├─ d: (never tried)
└─ m: (never tried)

Query b..:

match(0): 'b' → one door
match(1): '.' → fan out over b-node's doors: only 'a'
match(2): '.' → fan out over ba-node's doors: only 'd'
match(3): past end → is_word? ✓

The scary-sounding "26-way explosion" was, in practice, a fan of one. Real tries are sparse; wildcards are expensive only where the registry is genuinely dense.

The code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
 
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
 
    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True
 
    def search(self, word: str) -> bool:
        def match(i, node):
            if i == len(word):
                return node.is_word
            ch = word[i]
            if ch == '.':
                return any(match(i + 1, child)
                           for child in node.children.values())
            if ch not in node.children:
                return False
            return match(i + 1, node.children[ch])
 
        return match(0, self.root)

any() over a generator short-circuits: the first confirming branch stops the fan-out cold, exactly like the detective closing the file at the first match.

Gotchas

1. Dots in addWord. The contract says added words are plain letters. If you defensively handle dots on insert, you've built a different (and ambiguous) structure. Insert stores literals; only search interprets.

2. The flag check at the end, again. match past the last character must return node.is_word, not True. Query ba against "bad" reaches a real node, flagless. Boss 1's App-family lesson, restated under recursion.

3. Fanning over the alphabet instead of the doors. for ch in 'abcdefghijklmnopqrstuvwxyz' then checking existence works but does 26 lookups where node.children.values() touches only real doors. Same complexity class, sloppier constant, and it reads like you don't trust your own structure.

4. Early length check... that you can't do. Tempting: reject queries longer than the longest stored word. Fine as an optimization with bookkeeping, but within the walk, don't guess: the recursion's i == len(word) boundary is the single source of truth. Length mismatches die naturally at dead ends or flagless finals.

Complexity

addWord: O(L). search: O(L) with no dots; worst case with dots is O(total nodes in the trie), a query of all dots visits everything, though sparseness and short-circuiting make typical cases far cheaper.

Space: the trie itself, O(total letters added), plus O(L) recursion depth.

Boss down. XP gained.

"B, something, something" closes the case: one branch of the fan lands on a flag, and the suspect's alias is confirmed by a registry that never once scanned its full list of names.

What you walked away with:

• Wildcards turn the walk into a tree of attempts: fan out at the dot, over actual doors only
• any() + generator = short-circuiting search, first success ends everything
• The trie's sparseness is the pruning; structures that store dead ends must walk them
• Proto-backtracking: choose, descend, return, re-choose, Dungeon 9's opening move, previewed

One boss left in this short dungeon, and it's the crescendo: the trie leaves the registry and gets dragged across a grid, guiding a search through letter tiles in four directions. It's the problem this entire data structure gets hired for.

Next up: Boss 3 — The Treasure Grid. A farmer's field of letter tiles, a list of treasure words, and paths that snake through adjacent tiles. Searching the grid for each word separately drowns; planting the whole word list into one trie and walking the field once, pruning every path the trie doesn't bless, flies. Word Search II, the boss that makes grids and tries shake hands.