LeetCode 211 - Design Add and Search Words Data Structure

LeetCode Problem 211

Difficulty: 🟡 Medium
Topics: String, Depth-First Search, Design, Trie

Solution

Problem Understanding

The problem asks us to design a data structure that supports two operations efficiently:

1. Adding words into the structure.
2. Searching for words, where the search pattern may contain the wildcard character '.'.

The wildcard '.' represents any single lowercase English letter. This means that a search query is not always an exact string match. Instead, it may represent multiple possible strings.

For example, if the data structure contains the words "bad", "dad", and "mad":

• Searching for "bad" should return true
• Searching for ".ad" should also return true, because the dot can represent 'b', 'd', or 'm'
• Searching for "b.." should return true, because the two dots can represent any two characters

The input operations are performed incrementally. Words are added over time, and later searches must consider all previously added words.

The constraints provide important information about the scale of the problem:

• Each word has length between 1 and 25
• There are at most 10^4 operations total
• Search queries may contain at most 2 wildcard dots

These constraints suggest that a naive solution may still work in some cases, but we should aim for a more scalable structure that avoids repeatedly scanning all stored words. The wildcard behavior strongly hints that prefix-based traversal will be useful.

Several edge cases are important:

• Searching before any words are added
• Searching for words of different lengths
• Searching with only wildcard characters, such as ".." or "..."
• Adding duplicate words
• Wildcards appearing at the beginning, middle, or end of the query
• Queries that partially match many words before failing

A correct implementation must distinguish between prefixes and complete words. For example, if "bad" is added, searching for "ba" should still return false.

Approaches

Brute Force Approach

A straightforward solution is to store all added words in a list or set. When performing a search:

• If the query contains no dots, we can directly check membership in a set
• If the query contains dots, we iterate through every stored word and compare character by character

During comparison:

• Normal characters must match exactly
• Dots match any character
• Word lengths must be equal

This approach is correct because every stored word is checked against the pattern, so no possible match is missed.

However, this becomes inefficient as the number of stored words grows. Every wildcard search may require scanning all stored words, and each comparison costs up to the word length.

The worst case becomes expensive when there are many words and many wildcard searches.

Optimal Approach

The key observation is that searches operate character by character, and many words share common prefixes.

A Trie, also called a prefix tree, is ideal for this situation because:

• Each node represents a character
• Paths from root to leaf represent words
• Shared prefixes are stored only once
• Searches naturally follow character positions

For normal characters, we move to the corresponding child node.

For wildcard dots, we recursively explore all possible child nodes at that position.

This allows us to avoid scanning unrelated words entirely. Instead of checking every stored word, we only traverse paths that could possibly match the query.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × L) per wildcard search	O(N × L)	Scans all words and compares characters
Optimal Trie	O(L) average, branching on dots	O(N × L)	Efficient prefix-based traversal with DFS

Here:

• N is the number of stored words
• L is the maximum word length

Algorithm Walkthrough

Trie Structure

Each Trie node stores:

• A mapping of characters to child nodes
• A boolean flag indicating whether the node marks the end of a complete word

Add Word Operation

1. Start at the root node.
2. Process the word one character at a time.
3. For each character:

• Check whether a child node already exists.
• If not, create a new child node.
• Move to that child node.

4. After processing the final character:

• Mark the current node as the end of a valid word.

This structure allows many words with shared prefixes to reuse the same nodes.

Search Operation

1. Start a depth-first search from the root node and index 0.
2. At each recursive call:

• If the current index equals the word length:

• Return whether the current node marks a complete word.

3. Read the current character.
4. If the character is a normal letter:

• Check whether the corresponding child exists.
• If not, return false.
• Otherwise continue recursively with the child node and next index.

5. If the character is '.':

• Try every child node recursively.
• If any recursive call returns true, return true.
• If none succeed, return false.

6. The final result indicates whether at least one valid path matches the query.

Why it works

The Trie guarantees that every root-to-node path corresponds to a prefix of some inserted word. During search:

• Exact characters restrict traversal to one valid path.
• Wildcards explore all valid possibilities at that position.

Because the DFS explores every possible matching branch and only returns true when a complete stored word is matched, the algorithm is both complete and correct.

Python Solution

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_word = False

class WordDictionary:

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

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

        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()

            current = current.children[char]

        current.is_word = True

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

        def dfs(node: TrieNode, index: int) -> bool:
            if index == len(word):
                return node.is_word

            char = word[index]

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

            if char not in node.children:
                return False

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

        return dfs(self.root, 0)

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

The implementation begins with a TrieNode class. Each node stores:

• children, a dictionary mapping characters to child nodes
• is_word, which indicates whether a complete word ends at this node

The WordDictionary constructor initializes the Trie root.

The addWord method iterates through each character in the input word. If the corresponding child node does not exist, it creates one. After processing all characters, it marks the final node as a valid word ending.

The search method uses recursive depth-first search.

The recursive helper function dfs(node, index) represents the question:

"Can the suffix starting at index be matched from this Trie node?"

If the current character is a normal letter, traversal continues along exactly one child.

If the character is '.', the algorithm recursively explores every possible child node. If any branch succeeds, the search succeeds.

The recursion terminates successfully only when:

• Every character in the query has been processed
• The final node represents a complete stored word

Go Solution

type TrieNode struct {
	children map[byte]*TrieNode
	isWord   bool
}

type WordDictionary struct {
	root *TrieNode
}

func Constructor() WordDictionary {
	return WordDictionary{
		root: &TrieNode{
			children: make(map[byte]*TrieNode),
		},
	}
}

func (this *WordDictionary) AddWord(word string) {
	current := this.root

	for i := 0; i < len(word); i++ {
		char := word[i]

		if _, exists := current.children[char]; !exists {
			current.children[char] = &TrieNode{
				children: make(map[byte]*TrieNode),
			}
		}

		current = current.children[char]
	}

	current.isWord = true
}

func (this *WordDictionary) Search(word string) bool {

	var dfs func(node *TrieNode, index int) bool

	dfs = func(node *TrieNode, index int) bool {
		if index == len(word) {
			return node.isWord
		}

		char := word[index]

		if char == '.' {
			for _, child := range node.children {
				if dfs(child, index+1) {
					return true
				}
			}
			return false
		}

		nextNode, exists := node.children[char]

		if !exists {
			return false
		}

		return dfs(nextNode, index+1)
	}

	return dfs(this.root, 0)
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */

The Go implementation follows the same algorithmic structure as the Python version, but there are several language-specific differences.

Go uses map[byte]*TrieNode instead of Python dictionaries. Since the input only contains lowercase English letters, using byte is efficient and sufficient.

Pointers are used for Trie nodes so that child modifications affect the original structure.

The recursive DFS is implemented as a closure assigned to a variable. This allows the helper function to reference itself recursively.

Unlike Python, Go requires explicit existence checks when accessing map entries. The code uses:

nextNode, exists := node.children[char]

to safely determine whether a child node exists.

Worked Examples

Example Input

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")
search("bad")
search(".ad")
search("b..")

Trie State After Insertions

Word Added	Trie Paths
"bad"	b → a → d
"dad"	d → a → d
"mad"	m → a → d

Search "pad"

Step	Character	Current Possibilities	Result
1	'p'	Root children are b, d, m	No 'p' child
2	Stop	No valid path	false

Search "bad"

Step	Character	Traversal
1	'b'	Move to b node
2	'a'	Move to a node
3	'd'	Move to d node
4	End	is_word == true

Result is true.

Search ".ad"

Step	Character	Action
1	'.'	Try all root children
2	'a'	Match a under b, d, m
3	'd'	Match final d
4	End	At least one valid word found

Result is true.

Search "b.."

Step	Character	Action
1	'b'	Move to b node
2	'.'	Explore all children from a
3	'.'	Explore all children from d
4	End	Complete word matched

Result is true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(L × 26^D) worst case	DFS may branch for each dot
Space	O(N × L)	Trie stores all characters

Where:

• L is the word length
• D is the number of wildcard dots
• N is the number of inserted words

The branching factor comes from wildcard searches. In the worst case, each dot may require exploring up to 26 child nodes.

However, the problem guarantees at most 2 dots in search queries, which keeps the search efficient in practice.

The space complexity comes from storing Trie nodes. In the worst case, no prefixes are shared, so each character creates a new node.

Test Cases

# Basic example from problem statement
wd = WordDictionary()
wd.addWord("bad")
wd.addWord("dad")
wd.addWord("mad")

assert wd.search("pad") is False  # word does not exist
assert wd.search("bad") is True   # exact match
assert wd.search(".ad") is True   # wildcard at beginning
assert wd.search("b..") is True   # multiple wildcards

# Single character words
wd = WordDictionary()
wd.addWord("a")

assert wd.search("a") is True     # exact single character
assert wd.search(".") is True     # wildcard single character
assert wd.search("b") is False    # non-existing character

# Prefix should not count as full word
wd = WordDictionary()
wd.addWord("bad")

assert wd.search("ba") is False   # prefix only
assert wd.search("bad") is True   # full word exists

# Multiple branching wildcard paths
wd = WordDictionary()
wd.addWord("cat")
wd.addWord("car")
wd.addWord("cap")

assert wd.search("ca.") is True   # multiple valid endings
assert wd.search("c..") is True   # multiple wildcard matches
assert wd.search("cb.") is False  # invalid middle character

# Different word lengths
wd = WordDictionary()
wd.addWord("hello")

assert wd.search("hell") is False     # shorter word
assert wd.search("helloo") is False   # longer word

# Wildcards only
wd = WordDictionary()
wd.addWord("ab")
wd.addWord("cd")

assert wd.search("..") is True    # any two-letter word
assert wd.search("...") is False  # no three-letter word

# Duplicate insertions
wd = WordDictionary()
wd.addWord("test")
wd.addWord("test")

assert wd.search("test") is True  # duplicate insertion safe

# Search before adding words
wd = WordDictionary()

assert wd.search("a") is False    # empty dictionary
assert wd.search(".") is False    # wildcard on empty dictionary

Test Summary

Test	Why
Problem statement example	Verifies core functionality
Single character words	Tests smallest valid input
Prefix vs full word	Ensures end-of-word tracking
Multiple wildcard branches	Validates DFS branching
Different word lengths	Confirms exact length matching
Wildcards only	Tests fully generic searches
Duplicate insertions	Ensures idempotent behavior
Empty dictionary searches	Handles no-data edge case

Edge Cases

Prefix Exists but Full Word Does Not

A common bug occurs when implementations confuse prefixes with complete words.

For example, after inserting "bad", searching for "ba" should return false.

A Trie naturally stores prefixes during insertion, so the implementation must explicitly track whether a node represents the end of a complete word. This is why each node contains the is_word flag. The search only succeeds when the final node has is_word == True.

Wildcard Branch Explosion

Wildcard searches can potentially explore many branches.

For example:

search("...")

could recursively explore many combinations.

A naive implementation may accidentally revisit incorrect states or fail to stop early after finding a valid match.

The DFS implementation handles this correctly by:

• Exploring every child node for '.'
• Returning immediately once a valid path is found
• Returning false only if all branches fail

This guarantees correctness while avoiding unnecessary traversal after success.

Empty Trie Searches

Searching before any words are inserted is another important edge case.

For example:

search("a")
search(".")

should both return false.

Since the root node initially has no children, all searches immediately fail during traversal. The implementation safely handles this without special-case code because missing child checks naturally return false.