LeetCode 211: Design Add and Search Words Data Structure

Problem Restatement

We need to design a data structure that supports two operations:

The search query may contain lowercase letters and the special character:

.

A dot matches any one lowercase letter.

The official LeetCode problem asks us to implement WordDictionary with addWord and search, where search supports . as a wildcard matching any letter.

Input and Output

Class shape:

class WordDictionary:

    def __init__(self):
        ...

    def addWord(self, word: str) -> None:
        ...

    def search(self, word: str) -> bool:
        ...

Examples

Example:

wordDictionary = WordDictionary()
wordDictionary.addWord("bad")
wordDictionary.addWord("dad")
wordDictionary.addWord("mad")

wordDictionary.search("pad")
wordDictionary.search("bad")
wordDictionary.search(".ad")
wordDictionary.search("b..")

Results:

False
True
True
True

Why?

"pad" does not exist
"bad" exists
".ad" matches "bad", "dad", or "mad"
"b.." matches "bad"

Why a Hash Set Is Not Enough

For exact search, a hash set is simple.

words = {"bad", "dad", "mad"}

Then:

"bad" in words

works in constant time.

But wildcard search is harder.

For:

".ad"

we need to check all possible words that could match.

A set alone would require scanning many stored words.

We need a structure that supports prefix traversal and branching.

Key Insight: Trie Plus DFS

This problem is a direct extension of Trie.

A Trie is good for storing words character by character.

For normal letters, we follow one child.

For the wildcard ., we try every possible child.

That wildcard branching naturally becomes DFS.

Trie Node Design

Each node needs:

Node class:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

The is_word flag matters because a prefix and a complete word are different.

For example, after adding:

"bad"

the path:

b -> a

exists, but "ba" has not been added as a word.

So:

search("ba")

must return False.

Algorithm: addWord

To add a word:

1. Start at the root.
2. For each character:
   • If the child does not exist, create it.
   • Move to that child.
3. After the last character, mark the node as a complete word.

Example:

addWord("bad")

Creates this path:

root -> b -> a -> d

Then marks the d node as a word ending.

Algorithm: search

Search needs recursion because . can branch.

Define a DFS function:

dfs(index, node)

Meaning:

Can word[index:] match starting from this Trie node?

At each position:

• If the character is a normal letter, follow that child.
• If the character is ., try every child.
• If we reach the end of the pattern, return node.is_word.

Walkthrough

Suppose the dictionary contains:

bad
dad
mad

Trie shape:

root
├── b -> a -> d
├── d -> a -> d
└── m -> a -> d

Search:

".ad"

At index 0, the pattern has ..

So DFS tries all root children:

b
d
m

Try b.

Then remaining pattern is:

ad

a exists after b.

d exists after a.

End of pattern, and the node is marked as a word.

So return:

True

Search:

"pad"

At index 0, the pattern has p.

There is no p child at the root.

Return:

False

Correctness

The addWord method inserts each word as a path from the root to a terminal node. The final node is marked with is_word = True, so the structure records exactly which full words have been added.

The search method checks whether the query can match any inserted word.

For a normal letter, the next Trie edge must have that exact character. If the edge is missing, no stored word can match that query path.

For ., any lowercase letter may match, so the algorithm correctly tries every child node. If any branch succeeds, the wildcard query matches an inserted word.

When the search reaches the end of the query, the algorithm returns True only if the current node marks the end of a full inserted word. This prevents prefixes from being accepted as complete words.

Therefore search returns True exactly when at least one added word matches the query pattern.

Complexity

Let:

m = length of the word or query

For addWord:

For search:

In practice, Trie depth is limited by word length, and branching is constrained by stored words.

Space for the whole dictionary is:

O(total number of characters inserted)

Implementation

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 dfs(index: int, node: TrieNode) -> bool:
            if index == len(word):
                return node.is_word

            ch = word[index]

            if ch == ".":
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True

                return False

            if ch not in node.children:
                return False

            return dfs(index + 1, node.children[ch])

        return dfs(0, self.root)

Code Explanation

The Trie starts with an empty root node:

self.root = TrieNode()

Adding a word walks through the Trie:

for ch in word:

If the character path does not exist, create it:

if ch not in node.children:
    node.children[ch] = TrieNode()

After inserting every character, mark the final node:

node.is_word = True

For search, define DFS:

def dfs(index: int, node: TrieNode) -> bool:

If all query characters have been consumed:

if index == len(word):
    return node.is_word

This returns True only for a complete inserted word.

For wildcard:

if ch == ".":

try every child:

for child in node.children.values():
    if dfs(index + 1, child):
        return True

If no branch works:

return False

For a normal character, the path must exist:

if ch not in node.children:
    return False

Then continue with the matching child:

return dfs(index + 1, node.children[ch])

Iterative Exact Search Is Not Enough

A normal Trie lookup would work for queries without dots:

def search_exact(self, word: str) -> bool:
    node = self.root

    for ch in word:
        if ch not in node.children:
            return False

        node = node.children[ch]

    return node.is_word

But this cannot handle:

"b.."

because each dot needs branching.

That is why DFS is needed.

Testing

def run_tests():
    wd = WordDictionary()

    wd.addWord("bad")
    wd.addWord("dad")
    wd.addWord("mad")

    assert wd.search("pad") is False
    assert wd.search("bad") is True
    assert wd.search(".ad") is True
    assert wd.search("b..") is True
    assert wd.search("ba") is False
    assert wd.search("...") is True
    assert wd.search("....") is False

    wd.addWord("a")
    assert wd.search(".") is True
    assert wd.search("a") is True
    assert wd.search("b") is False

    print("all tests passed")

run_tests()