Design Add and Search Words Data Structure - Solution & Explanation

MediumString Depth-First Search Design Trie22 min readAsked at: Amazon, Microsoft, Apple +10

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 10⁴ calls will be made to addWord and search.

Approach Overview

Problem Overview: Build a data structure that supports two operations: addWord(word) to store a word and search(pattern) to check if any stored word matches the pattern. The search pattern may include the wildcard ., which matches any single character.

Approach 1: HashMap with DFS for Wildcards (Time: add O(m), search O(n * 26^w), Space: O(n*m))

Store words grouped by length using a HashMap<length, List<word>>. During search, only compare words of the same length as the query. Iterate through each candidate word and check character-by-character, treating . as a match for any character. This approach avoids scanning irrelevant lengths but still requires scanning many candidates when the dictionary grows. It works well for small datasets but degrades when many words share the same length.

Approach 2: Backtracking with Pattern Matching (Time: worst case O(26^w * m), Space: O(m) recursion)

During search, recursively explore possible character matches whenever a . appears. Each wildcard branches into multiple possibilities, effectively performing backtracking over possible character substitutions. This technique demonstrates how wildcard matching works conceptually, but without a specialized structure it repeatedly scans strings and becomes inefficient as the dataset grows. It mainly serves as an intermediate idea before introducing a trie.

Approach 3: Trie Data Structure with DFS (Time: add O(m), search average O(m), worst O(26^w * m), Space: O(n*m))

Insert each word into a Trie, where each node represents a character. addWord simply iterates through characters and creates nodes if missing. For search, traverse the trie normally until encountering .. When a wildcard appears, run a DFS across all child nodes and continue matching the remaining characters. This structure drastically prunes the search space because only valid prefixes are explored. The trie efficiently supports prefix traversal and wildcard branching while keeping operations proportional to the word length.

Recommended for interviews: The trie-based solution is what interviewers expect. It shows you understand prefix trees, branching search with DFS, and how to optimize wildcard pattern matching. Mentioning the naive length-bucket scan demonstrates baseline reasoning, but implementing the trie shows strong command of string indexing and data structure design.

Approach 1: Approach 1: Trie-based Implementation

This approach involves using a Trie data structure, which is highly efficient for dynamic prefix search operations. Each node of the Trie represents a character of a string. For the search operation, if the current character is a dot '.', then recursively search all possible nodes. This allows the Trie to handle strings with wildcard characters.

The Python implementation initializes a Trie structure with a root node. addWord iterates through the characters of the word and constructs nodes if they do not exist. search checks each character. When it encounters a '.', it branches out recursively to all children nodes. This efficiently handles wildcard searches.

Code

Python

Complexity

Time Complexity: O(n) for addWord and O(m^26) in the worst case for search where m is the length of the word.
Space Complexity: O(total_characters) for the trie structure.

Try this approach in the editor →

Approach 2: Approach 2: HashMap with DFS for Wildcards

This approach uses a combination of a HashMap (Dictionary in some languages) to store words based on their lengths. The search checks the word's length first and retrieves potential matches. For wildcards, a Depth-First Search (DFS) explores possible character matches sequentially.

The Java solution uses a HashMap to categorize words by their length, providing O(1) access to words of the same size during the search. The DFS-like isMatch function is straightforward, checking corresponding positions of candidate words and query words. It allows efficient handling of the '.' wildcard.

Code

Java

Complexity

Time Complexity: O(m*n) for search, where m is the number of words of the same length and n is the length of the word.
Space Complexity: O(total_chars) for storing words in the HashMap.

Try this approach in the editor →

Approach 3: Approach 1: Using Trie Data Structure

Tries, also known as prefix trees, are efficient for searching words by prefixes and can be adapted to handle wildcard characters. In this approach:

Create a TrieNode class with a dictionary to store child nodes and a boolean flag to represent the end of a word.
To add a word, traverse the trie according to each character in the word, creating new nodes as needed, and finally mark the end of the word.
To search a word, if the character is a '.', recursively check all possible nodes at the current level; otherwise, follow the specific path.

The Python code defines a WordDictionary class using a TrieNode class for node representation. The addWord function inserts a word into the trie. The search function handles '.' using a recursive DFS approach, allowing branching wherever a dot is encountered.

Code

Python Java C C++C#JavaScript

Python

Java

C++

JavaScript

Complexity

Time Complexity: O(n) for adding a word and average of O(n*m) for searching a word, where n is the length of the word and m is the branching factor of the trie. Space Complexity: O(n*m) for storing words in the trie.

Try this approach in the editor →

Approach 4: Approach 2: Backtracking

In this approach, we utilize backtracking for the search operation. This approach is simpler in terms of implementation but may not be as efficient as using a Trie due to repetitive computations:

Maintain a list of words.
For the addWord function, simply add the word to the list.
For the search function, iterate through each stored word, and use recursion to handle '.' in the search query, comparing matching paths or using any letter at wildcard positions.

The Python solution implements WordDictionary using a list to store words. The addWord method appends words to the list, and search checks each word for matching pattern lengths and characters or wildcards using helper function.

Code

Python Java C C++C#JavaScript

Python

Java

C++

JavaScript

Complexity

Time Complexity: O(m * n) for search, where m is the number of words and n is the average length of the longest word. Space Complexity: O(t * l) for the list, where t is the total words stored, and l is their average length.

Try this approach in the editor →

Approach 5: Default Approach

Code

Python Java C++Go C#

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Trie-based Implementation	Time Complexity: O(n) for addWord and O(m^26) in the worst case for search where m is the length of the word. Space Complexity: O(total_characters) for the trie structure.
Approach 2: HashMap with DFS for Wildcards	Time Complexity: O(m*n) for search, where m is the number of words of the same length and n is the length of the word. Space Complexity: O(total_chars) for storing words in the HashMap.
Approach 1: Using Trie Data Structure	Time Complexity: O(n) for adding a word and average of O(nm) for searching a word, where n is the length of the word and m is the branching factor of the trie. Space Complexity: O(nm) for storing words in the trie.
Approach 2: Backtracking	Time Complexity: O(m * n) for search, where m is the number of words and n is the average length of the longest word. Space Complexity: O(t * l) for the list, where t is the total words stored, and l is their average length.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
HashMap by Word Length	Add: O(m), Search: O(n*m)	O(n*m)	Simple implementation when dataset is small and wildcard searches are rare
Backtracking Pattern Match	Worst O(26^w * m)	O(m)	Conceptual wildcard exploration without building specialized structures
Trie with DFS	Add: O(m), Search: avg O(m), worst O(26^w * m)	O(n*m)	Best general solution for frequent searches and wildcard queries

Video Solution

Design Add and Search Words Data Structure - Leetcode 211 - Python • NeetCode • 158,008 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Add and Search Words Data Structure easy or hard?

The problem is rated Medium on LeetCode. The difficulty comes from combining trie traversal with DFS to support wildcard characters. Understanding how to branch search paths efficiently is the key insight.

Design Add and Search Words Data Structure Python/Java solution

The standard solution uses a Trie class where each node contains a map or array of children and a boolean end-of-word flag. Python implementations typically use dictionaries for children, while Java often uses arrays or HashMaps. The search function performs DFS when encountering '.' to explore multiple branches.

How to solve Design Add and Search Words Data Structure in O(n)?

Insertion is O(m) using a trie because each character is processed once. Search is also close to O(m) when the pattern has no wildcards. The trie ensures you only traverse valid prefixes instead of scanning all stored words, which keeps operations proportional to word length rather than dictionary size.

What is the best approach for Design Add and Search Words Data Structure?

The trie-based approach with DFS is the most efficient and commonly expected solution. Words are stored in a prefix tree, and wildcard '.' characters trigger a DFS across child nodes. Adding a word takes O(m) time where m is the word length, and search is typically O(m) but may branch to O(26^w * m) in worst cases with many wildcards.

Is Design Add and Search Words Data Structure asked at Google/Amazon/Meta?

Trie design problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test data structure design, recursion, and efficient string handling. Variations of this problem also appear in autocomplete systems and dictionary search features.

What data structure is used in Design Add and Search Words Data Structure?

The primary data structure is a Trie (prefix tree). Each node stores child pointers for characters and a flag marking the end of a word. During search, DFS is used when encountering the '.' wildcard to explore all valid character branches.

What is the time complexity of Design Add and Search Words Data Structure?

Using a trie, addWord runs in O(m) time where m is the length of the word. Search usually runs in O(m) for normal characters. If the pattern contains w wildcard '.' characters, the worst-case complexity becomes O(26^w * m) because each wildcard can branch into multiple child nodes.

Ready to solve this problem?

Practice Design Add and Search Words Data Structure with our built-in code editor and test cases.

Practice on FleetCode

Count Prefix and Suffix Pairs I

Count Prefix and Suffix Pairs II

Problem Info

DifficultyMedium

Acceptance48.9%

Approaches5

Reading time22 min

Asked at

Amazon Microsoft Apple Meta Oracle

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Trie-based Implementation

Code

Complexity

Approach 2: Approach 2: HashMap with DFS for Wildcards

Code

Complexity

Approach 3: Approach 1: Using Trie Data Structure

Code

Complexity

Approach 4: Approach 2: Backtracking

Code

Complexity

Approach 5: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents