Skip to content

Volume ITechnology

4.15.2 — Design Add and Search Words Data Structure ​

LeetCode 211 · Medium · ★ Blind 75

The problem ​

Support addWord(word) and search(word), where the search string may contain . as a wildcard matching any single character.

addWord("bad"); addWord("dad"); addWord("mad")
search("pad")  →  false
search("bad")  →  true
search(".ad")  →  true
search("b..")  →  true

The pattern ​

The trie from 4.15.1 is unchanged. Only search changes.

Without wildcards, search is a straight walk: at each character there is exactly one child to follow, or the word is absent.

A . breaks that. Any child could be the right one, and you cannot tell which without looking. So the search branches: try every child, and succeed if any branch succeeds.

Think of it like being in a maze where most doors are labeled with a specific letter, but you have a wild-card key . that can unlock any door. When you hit a regular letter, you just take that one specific door. But when you hit ., you don't know which door leads to the exit, so you have to peek into all of them, one by one, and see if any path gets you to the end.

A search that branches and may need to back out is a depth-first search with backtracking. So the iterative walk becomes recursive.

The solution ​

python
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:  # (1)
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(index: int, node) -> bool:  # (2)
            for i in range(index, len(word)):  # (3)
                c = word[i]

                if c == '.':                                  # (4) try every child
                    for child in node.children.values():  # (5)
                        if dfs(i + 1, child):
                            return True
                    return False                              # (6) no child worked

                if c not in node.children:  # (7)
                    return False
                node = node.children[c]  # (8)

            return node.is_word  # (9)

        return dfs(0, self.root)  # (10)
ts
class WordDictionary {
  private root = new TrieNode();

  addWord(word: string): void {  // (1)
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isWord = true;
  }

  search(word: string): boolean {
    const dfs = (index: number, start: TrieNode): boolean => {  // (2)
      let node = start;
      for (let i = index; i < word.length; i++) {  // (3)
        const c = word[i];

        if (c === '.') {  // (4)
          for (const child of node.children.values()) {  // (5)
            if (dfs(i + 1, child)) return true;
          }
          return false;                                  // (6)
        }

        const next = node.children.get(c);
        if (!next) return false;                         // (7)
        node = next;                                     // (8)
      }
      return node.isWord;                                // (9)
    };

    return dfs(0, this.root);                            // (10)
  }
}

Line by line ​

(1) addWord is exactly insert from 4.15.1. Only searching changes.

(2) A search that can branch. dfs(index, node) answers: "starting at position index of the pattern, standing on node, can the rest of the pattern be matched?"

(3) Walk the pattern from index onward, one character per step.

(4) A wildcard. A . may stand for any letter, so one step now has many possible next nodes.

(5) Try every child. For each one, ask whether the rest of the pattern, from i + 1, can be matched starting at that child. If any child works, the whole search succeeds.

(6) No child worked, so this branch has failed. This return False is essential. Without it, the code would fall through and keep walking from the wrong node.

(7) An ordinary letter with no matching child. No stored word fits, so fail.

(8) An ordinary letter that matches. Step down, exactly as in a normal trie walk. No recursion is needed here, because there is only one way to go.

(9) The pattern is used up. A path exists, but it only counts if a stored word ends exactly here. So return the flag, not True.

(10) Start the search at the root, from position 0 of the pattern.

The loop handles ordinary characters iteratively and only recurses on a wildcard. That keeps the recursion depth proportional to the number of dots rather than to the word length, which matters for long words with few wildcards.

The return False after the wildcard loop is essential. If no child leads to a match, this branch has failed and must say so. Falling through would continue the outer loop from the wrong node.

return node.is_word at the end, not return True. Reaching the end of the search string only means a path exists; whether it spells a stored word is what the flag says. This is the same distinction as search versus startsWith in 4.15.1.

Trace ​

Words bad, dad, mad. Search ".ad".

At the root, the first character is ., so try each child in turn: b, d, m.

Following b: the remaining pattern is "ad", which walks a then d and lands on a node with is_word set. Return true, and the other branches are never tried.

Search "b.." walks b deterministically, then branches on the first dot — but b has only the child a, so there is only one branch, and then only one more. It matches.

Complexity ​

Without wildcards: O(L) for a word of length L, exactly as before.

With wildcards: each . multiplies the work by the number of children at that node, up to 26. So the worst case is O(26^d \cdot L) where d is the number of dots.

In practice it is far cheaper, because most branches die immediately — a real trie is sparse, and a node rarely has all 26 children.

A leading . is the expensive case, because the root usually does have many children. A dot deep in the word costs almost nothing.

Space is O(\text{total characters added}).

Edge cases ​

  • A pattern made only of dots, like "...". It matches any stored word of exactly that length. This is the slowest case, because every level branches.
  • A pattern longer than every stored word. Every path runs out, and the answer is false.
  • A pattern that matches a prefix but not a whole word, like ".a" when only "bad" is stored. The path exists, but the flag check in line (9) fails.

Where this goes next ​

  • Word Search II — a trie plus backtracking over a grid instead of a string. That is 4.15.3, and it is the same combination taken further.
  • Regular Expression Matching — . plus *, which needs dynamic programming because a star can match any number of characters and greedy branching no longer terminates cleanly. 4.24.
  • Wildcard Matching — ? and * against a single string, also DP.

The rule: a deterministic walk becomes a depth-first search the moment a step has more than one legal continuation.

What the interviewer will push on ​

"What is the worst-case complexity?" O(26^d \cdot L) for d wildcards, and say that a leading dot is the expensive position.

"Why recursion here but not in the plain trie?" Because a wildcard makes the walk branch, and a branch that can fail needs to back out.

"Why return node.is_word and not return True?" A path existing is not the same as a word ending there.

"How would you handle * as well?" That is a different problem — a star matches any number of characters, so the search space stops being a simple tree walk and you move to DP.

"Could you speed up many wildcard searches?" If searches are frequent and the word set is fixed, index words by length and by known character positions, so a pattern only ever searches the words that could possibly match.

One thing to volunteer: say that only search changes, and that the change is exactly "one child becomes all children". Naming the minimal difference from the previous problem is a strong signal.

Next: 4.15.3 Word Search II — the hardest problem in this group, where a trie turns an impossible search into a fast one.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet