Design Add and Search Words Data Structure

Table of Contents +

A plain trie can find an exact word fast. But what if you do not know one of the letters? Crossword apps face this all the time. You know “b.d” matches “bad” or “bed” but you are not sure which. This question takes the trie one step further and adds a wildcard.

🎯 The Problem

You have to design a small word dictionary with a wildcard search.

addWord(word) stores a word.
search(word) returns true if the word is in the dictionary.
The search word may contain a dot ..
The dot is a wildcard, a placeholder that matches any single letter.
So search("b.d") is true if any stored word starts with b and ends with d and has one letter between.

Operations:
  addWord("bad")
  addWord("dad")
  addWord("mad")
  search("pad")   -> false   (we never added "pad")
  search("bad")   -> true
  search(".ad")   -> true     (dot matches b, d, or m)
  search("b..")   -> true     (two dots match a and d)

A plain search walks one fixed path. But a dot must try every child. So one dot turns one path into many paths to explore.

Here is the trie after adding “bad”, “dad” and “mad”. They all share the ending a, d but start with three different letters.

🐢 Approach 1: Store and Scan (Brute Force)

The idea in one line: keep all words in a list and compare each to the pattern.

The idea:

addWord pushes the word onto a list.
search walks the list and compares each stored word to the pattern.
Treat a dot as “always matches” during the compare.

How it works:

For each word, line up its letters with the pattern.
A real letter must match. A dot matches anything.

Why it is weak:

Each search scans every stored word.
The dot lets you skip nothing here. You still test every word fully.
With many words this gets slow.

Here is the store-and-scan code:

class WordDictionary:
    def __init__(self):
        self.words = []

    def addWord(self, word):
        self.words.append(word)

    def search(self, word):
        for candidate in self.words:
            if len(candidate) == len(word) and all(a == b or b == "." for a, b in zip(candidate, word)):
                return True
        return False

⚡ Approach 2: Trie Plus DFS Branching (Best)

The idea in one line: store words in a trie, and for a dot, branch into every child.

The idea:

Build a trie, the same prefix tree as before.
Each node has a map of children and an isEnd flag for a complete word.
addWord is the normal trie insert.
A normal letter does one move. A dot must try all children.

How search works:

It is a small recursive function over the pattern, an index, and a node.
A real letter moves into that one child and recurses on the next index.
A dot loops over every child and recurses into each. This branching is DFS, depth-first search.
The moment any branch reports a match, return true.
When the index reaches the pattern end, return the node’s isEnd flag. A real word must end there.

Why it is fast for plain words:

A pattern with no dots follows one path, so it costs O(L) for length L.
Only dots cause branching.

Here is how search(".ad") branches. The dot tries b, d and m, then each branch walks a then d.

Steps to Solve

Build a trie node with a children map and an isEnd flag.
addWord walks the letters and creates missing children, then sets isEnd on the last node.
For search, write a recursive helper that takes the pattern, an index, and a node.
If the index reached the end of the pattern, return the node’s isEnd.
If the character is a real letter, recurse into that one child if it exists.
If the character is a dot, recurse into every child and return true if any branch matches.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version stores children in a dictionary and uses a recursive dfs for the dot.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> child node
        self.is_end = False  # word ends here?


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.is_end = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word):            # used up the pattern
                return node.is_end        # need a real word end here
            ch = word[i]
            if ch == ".":                 # wildcard: try every child
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            if ch not in node.children:   # letter missing
                return False
            return dfs(node.children[ch], i + 1)  # one fixed child

        return dfs(self.root, 0)


d = WordDictionary()
d.add_word("bad")
d.add_word("dad")
d.add_word("mad")
print(d.search("pad"))
print(d.search("bad"))
print(d.search(".ad"))
print(d.search("b.."))

The output of the above code will be:

False
True
True
True

Let us read the Python search line by line, since the branching lives there.

def dfs(node, i) is a helper that remembers two things. node is where we stand in the trie. i is how far we have read into the pattern. The line if i == len(word): return node.is_end is the stop point. When the pattern is used up, a match only counts if a real word ended here, so we return the flag.

ch = word[i] reads the current pattern character. The branch if ch == "." is the wildcard case. We loop for child in node.children.values() and recurse into each child with dfs(child, i + 1). If any child returns True, we return True right away. That early return is what makes DFS efficient, since we stop as soon as one branch works.

The line if ch not in node.children: return False handles a normal letter that has no path. If the letter does exist, return dfs(node.children[ch], i + 1) moves into that single child and continues. So a real letter never branches, only the dot does.

⏱️ Time and Space Complexity

A normal letter does one move. A dot may try every child of a node. Let L be the pattern length and let the branching factor be how many children a node has, up to 26 for lowercase letters. With no dots, search is O(L). With many dots near the start, the worst case branches into many paths. So a dot-heavy pattern can cost up to O(26^L) in the worst case, though real dictionaries are far smaller.

Operation	Time Complexity	Space Complexity
addWord (length L)	O(L)	O(L)
search with no dots	O(L)	O(L) recursion
search with many dots (worst case)	O(26^L)	O(L) recursion

Tip

The interviewer mainly wants to see that you handle the dot with a loop over children plus recursion. Say clearly that a real letter takes one path but a dot fans out into many. That sentence shows you understand why the worst case grows.

🧩 Key Takeaways

✅ Build the same trie as a plain prefix tree, with a children map and an isEnd flag.
✅ addWord is the ordinary trie insert.
✅ Search becomes a recursive DFS so a dot can branch into every child.
✅ A real letter follows one path, but a dot tries all children and returns true if any branch matches.
✅ When the pattern ends, the answer is the isEnd flag of the node you land on.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Implement Trie (Prefix Tree)
Word Search II

Previous Implement Trie (Prefix Tree) Next Word Search II

Design Add and Search Words Data Structure

Follow Us

Follow Us