Design Add And Search Words Data Structure

This is the same trie as Implement Trie Prefix Tree, plus one wrinkle: search can contain . wildcards that match any single character. A plain iterative walk cannot handle that, because a . might need to try several children before one of them leads to a match — so search becomes a small DFS over the trie instead of a straight-line walk.

Brute Force: Words Grouped by Length

Time addWord O(L), search O(n·L)Space O(n·L)

Since a . matches exactly one character, a query can only ever match words of the same length. Bucket stored words by length, then for a query, scan only the bucket of matching length and compare position by position, treating . as a wildcard.

from collections import defaultdict

class WordDictionary:
    def __init__(self):
        self.by_len = defaultdict(list)

    def addWord(self, word: str) -> None:
        self.by_len[len(word)].append(word)

    def search(self, word: str) -> bool:
        for candidate in self.by_len[len(word)]:
            if all(w == '.' or w == c for w, c in zip(word, candidate)):
                return True
        return False

Grouping by length prunes obviously-wrong candidates, but within a bucket every word is still compared character by character in the worst case — O(n·L) for a search that matches late or not at all, where n is the number of words of that length.

Trie + DFS for Wildcards

OptimalTime addWord O(L), search O(26^d · L)Space O(total characters inserted)

Store words in a trie exactly as before. addWord is the same walk-and-create as insert. search also walks the trie, but on a . it cannot pick one child — it must try every child at that position and succeed if any of them leads to a full match. That is a DFS with backtracking, not a loop.

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:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_word
            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1) for child in node.children.values())
            if ch not in node.children:
                return False
            return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)

The trace below follows search walking a trie that already holds bad, dad and mad; watch how a . turns one position into several candidate branches and how a dead branch would send the walk back to try the next one.

Searching

pad

Results

pad Fbad ....ad ...b.. ...

•

Children here

bdm

DFS path

•

Verdictreturn false

1 / 13

currentseencomparingresultdiscarded

search(pad): the root has no p child, so the literal walk stops at once. A missing letter anywhere means the word was never added.

Complexity: addWord is O(L), unchanged from a plain trie. search is O(L) when there are no dots, but each dot can branch into up to 26 children, so a query with d dots costs O(26^d · L) in the worst case. The constraints cap dots at 2 per query, which keeps this fast in practice even though the theoretical worst case has exponential branching.

Design Add And Search Words Data Structure

Brute Force: Words Grouped by Length

Trie + DFS for Wildcards

More Tries practice