Design Add and Search Words Data Structure solution and explanation
Google
9 more videos on this problem
Design Add and Search Words Data Structure - Leetcode 211 - PythonNeetCode · 19:50 · 158K views
Design Add and Search Words Data Structure | Made Easy | GOOGLE | Leetcode 211codestorywithMIK · 25:08 · 7K views
Design Add and Search Words Data Structure - Leetcode - 211Algorithms Made Easy · 4:42 · 2K views
Design Add and Search Words Data Structure #leetcode #blind75Deepti Talesra · 15:35 · 1K views
Design Add And Search Word Data Structure - LeetCode 211 - Google InterviewAlgoJS · 7:30 · 1K views
Add And Search Word | LeetCode 211 (Medium) TrieDestination FAANG · 15:58 · 1K views
Design Add and Search Words Data Structure | Leeetcode 211 | Live coding session 🔥🔥🔥 | Easy TriesCoding Decoded · 2:34 · 625 views
Design Add and Search Words Data Structure | LeetCode 211 | JavaThe TryIt Project · 13:03 · 536 views
Design Add and Search Words Data Structure - TrieMastering Programming · 11:31 · 191 views
LeetCode 211 - Design Add and Search Words Data Structure [Daily Challenge]Code with Carter · 13:50 · 169 views
The problem
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)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay 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 <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of'.'or lowercase English letters.- There will be at most
2dots inwordforsearchqueries. - At most
104calls will be made toaddWordandsearch.
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.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
def search_in_node(word, node):
for i, char in enumerate(word):
if char == '.':
for child in node.children.values():
if search_in_node(word[i + 1:], child):
return True
return False
else:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
return search_in_node(word, self.root)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.
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: 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.
import java.util.*;
class WordDictionary {
private HashMap<Integer, List<String>> map;
public WordDictionary() {
map = new HashMap<>();
}
public void addWord(String word) {
int length = word.length();
map.putIfAbsent(length, new ArrayList<>());
map.get(length).add(word);
}
public boolean search(String word) {
int length = word.length();
if (!map.containsKey(length)) return false;
for (String candidate : map.get(length)) {
if (isMatch(candidate, word)) return true;
}
return false;
}
private boolean isMatch(String candidate, String word) {
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) != '.' && word.charAt(i) != candidate.charAt(i)) {
return false;
}
}
return true;
}
}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.
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 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.
class TrieNode:
def __init__(self):
self.children = {}
self.end_of_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.end_of_word = True
def search(self, word: str) -> bool:
def dfs(j, node):
for i in range(j, len(word)):
char = word[i]
if char == '.':
return any(dfs(i + 1, child) for child in node.children.values())
else:
if char not in node.children:
return False
node = node.children[char]
return node.end_of_word
return dfs(0, self.root)class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean endOfWord;
}
class WordDictionary {
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void addWord(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (node.children[ch - 'a'] == null) {
node.children[ch - 'a'] = new TrieNode();
}
node = node.children[ch - 'a'];
}
node.endOfWord = true;
}
public boolean search(String word) {
return searchInNode(word, root);
}
private boolean searchInNode(String word, TrieNode node) {
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (ch == '.') {
for (TrieNode child : node.children) {
if (child != null && searchInNode(word.substring(i + 1), child)) {
return true;
}
}
return false;
} else {
node = node.children[ch - 'a'];
if (node == null) {
return false;
}
}
}
return node.endOfWord;
}
}#include <vector>
using namespace std;
class TrieNode {
public:
vector<TrieNode*> children;
bool endOfWord;
TrieNode() : children(26, nullptr), endOfWord(false) {}
};
class WordDictionary {
TrieNode* root;
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children[ch - 'a'] == nullptr) {
node->children[ch - 'a'] = new TrieNode();
}
node = node->children[ch - 'a'];
}
node->endOfWord = true;
}
bool search(string word) {
return searchInNode(word, root);
}
private:
bool searchInNode(string word, TrieNode* node) {
for (int i = 0; i < word.size(); i++) {
char ch = word[i];
if (ch == '.') {
for (TrieNode* child : node->children) {
if (child != nullptr && searchInNode(word.substr(i + 1), child)) {
return true;
}
}
return false;
} else {
node = node->children[ch - 'a'];
if (node == nullptr) {
return false;
}
}
}
return node->endOfWord;
}
};class TrieNode {
constructor() {
this.children = {};
this.endOfWord = false;
}
}
class WordDictionary {
constructor() {
this.root = new TrieNode();
}
addWord(word) {
let node = this.root;
for (let ch of word) {
if (!node.children[ch]) {
node.children[ch] = new TrieNode();
}
node = node.children[ch];
}
node.endOfWord = true;
}
search(word) {
const searchInNode = (word, node) => {
for (let i = 0; i < word.length; i++) {
const ch = word[i];
if (ch === '.') {
for (let child in node.children) {
if (node.children[child] && searchInNode(word.slice(i + 1), node.children[child])) {
return true;
}
}
return false;
} else {
if (!node.children[ch]) {
return false;
}
node = node.children[ch];
}
}
return node.endOfWord;
}
return searchInNode(word, this.root);
}
}#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
typedef struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
bool endOfWord;
} TrieNode;
TrieNode* createTrieNode() {
TrieNode *node = (TrieNode*) malloc(sizeof(TrieNode));
node->endOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
node->children[i] = NULL;
return node;
}
typedef struct {
TrieNode *root;
} WordDictionary;
WordDictionary* wordDictionaryCreate() {
WordDictionary *obj = (WordDictionary*) malloc(sizeof(WordDictionary));
obj->root = createTrieNode();
return obj;
}
void wordDictionaryAddWord(WordDictionary* obj, char * word) {
TrieNode *node = obj->root;
for (int i = 0; i < strlen(word); i++) {
int index = word[i] - 'a';
if (node->children[index] == NULL)
node->children[index] = createTrieNode();
node = node->children[index];
}
node->endOfWord = true;
}
bool searchInNode(char *word, TrieNode *node) {
for (int i = 0; i < strlen(word); i++) {
if (word[i] == '.') {
for (int j = 0; j < ALPHABET_SIZE; j++) {
if (node->children[j] != NULL && searchInNode(word + i + 1, node->children[j])) {
return true;
}
}
return false;
} else {
int index = word[i] - 'a';
if (node->children[index] == NULL) {
return false;
}
node = node->children[index];
}
}
return node->endOfWord;
}
bool wordDictionarySearch(WordDictionary* obj, char * word) {
return searchInNode(word, obj->root);
}
void wordDictionaryFree(WordDictionary* obj) {
// Recursive free logic here
free(obj);
}public class TrieNode {
public TrieNode[] children = new TrieNode[26];
public bool EndOfWord;
}
public class WordDictionary {
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
public void AddWord(string word) {
TrieNode node = root;
foreach (char ch in word) {
if (node.children[ch - 'a'] == null) {
node.children[ch - 'a'] = new TrieNode();
}
node = node.children[ch - 'a'];
}
node.EndOfWord = true;
}
public bool Search(string word) {
return SearchInNode(word, root);
}
private bool SearchInNode(string word, TrieNode node) {
for (int i = 0; i < word.Length; i++) {
char ch = word[i];
if (ch == '.') {
foreach (TrieNode child in node.children) {
if (child != null && SearchInNode(word.Substring(i + 1), child)) {
return true;
}
}
return false;
} else {
node = node.children[ch - 'a'];
if (node == null) {
return false;
}
}
}
return node.EndOfWord;
}
}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.
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.
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
addWordfunction, simply add the word to the list. - For the
searchfunction, iterate through each stored word, and use recursion to handle '.' in the search query, comparing matching paths or using any letter at wildcard positions.
class WordDictionary:
def __init__(self):
self.words = []
def addWord(self, word: str) -> None:
self.words.append(word)
def search(self, word: str) -> bool:
def match(w1, w2):
for c1, c2 in zip(w1, w2):
if c2 != '.' and c1 != c2:
return False
return True
return any(len(w) == len(word) and match(w, word) for w in self.words)import java.util.ArrayList;
import java.util.List;
class WordDictionary {
private List<String> words;
public WordDictionary() {
words = new ArrayList<>();
}
public void addWord(String word) {
words.add(word);
}
public boolean search(String word) {
for (String w : words) {
if (w.length() == word.length() && isMatch(w, word)) {
return true;
}
}
return false;
}
private boolean isMatch(String w, String pattern) {
for (int i = 0; i < pattern.length(); i++) {
if (pattern.charAt(i) != '.' && w.charAt(i) != pattern.charAt(i)) {
return false;
}
}
return true;
}
}#include <vector>
#include <string>
using namespace std;
class WordDictionary {
vector<string> words;
public:
void addWord(string word) {
words.push_back(word);
}
bool search(string word) {
for (const string& w : words) {
if (w.length() == word.length() && isMatch(w, word)) {
return true;
}
}
return false;
}
bool isMatch(const string& w, const string& pattern) {
for (int i = 0; i < pattern.size(); i++) {
if (pattern[i] != '.' && w[i] != pattern[i]) {
return false;
}
}
return true;
}
};class WordDictionary {
constructor() {
this.words = [];
}
addWord(word) {
this.words.push(word);
}
search(word) {
return this.words.some(w => w.length === word.length && this.isMatch(w, word));
}
isMatch(w, pattern) {
for (let i = 0; i < pattern.length; i++) {
if (pattern[i] !== '.' && w[i] !== pattern[i]) {
return false;
}
}
return true;
}
}#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX_WORDS 10000
char* wordList[MAX_WORDS];
int wordCount = 0;
void wordDictionaryAddWord(char* word) {
wordList[wordCount++] = strdup(word);
}
bool isMatch(const char* word, const char* pattern) {
for (int i = 0; i < strlen(pattern); i++) {
if (pattern[i] != '.' && word[i] != pattern[i]) return false;
}
return true;
}
bool wordDictionarySearch(const char* pattern) {
for (int i = 0; i < wordCount; i++) {
if (strlen(wordList[i]) == strlen(pattern) && isMatch(wordList[i], pattern)) {
return true;
}
}
return false;
}using System.Collections.Generic;
public class WordDictionary {
private List<string> words;
public WordDictionary() {
words = new List<string>();
}
public void AddWord(string word) {
words.Add(word);
}
public bool Search(string word) {
foreach (var w in words) {
if (w.Length == word.Length && IsMatch(w, word)) {
return true;
}
}
return false;
}
private bool IsMatch(string word, string pattern) {
for (int i = 0; i < pattern.Length; i++) {
if (pattern[i] != '.' && word[i] != pattern[i]) {
return false;
}
}
return true;
}
}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.
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.
Approach 5: Default Approach
type WordDictionary struct {
root *trie
}
func Constructor() WordDictionary {
return WordDictionary{new(trie)}
}
func (this *WordDictionary) AddWord(word string) {
this.root.insert(word)
}
func (this *WordDictionary) Search(word string) bool {
n := len(word)
var dfs func(int, *trie) bool
dfs = func(i int, cur *trie) bool {
if i == n {
return cur.isEnd
}
c := word[i]
if c != '.' {
child := cur.children[c-'a']
if child != nil && dfs(i+1, child) {
return true
}
} else {
for _, child := range cur.children {
if child != nil && dfs(i+1, child) {
return true
}
}
}
return false
}
return dfs(0, this.root)
}
type trie struct {
children [26]*trie
isEnd bool
}
func (t *trie) insert(word string) {
cur := t
for _, c := range word {
c -= 'a'
if cur.children[c] == nil {
cur.children[c] = new(trie)
}
cur = cur.children[c]
}
cur.isEnd = true
}
/**
* Your WordDictionary object will be instantiated and called as such:
* obj := Constructor();
* obj.AddWord(word);
* param_2 := obj.Search(word);
*/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. |
| 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. |
| Approach 1: Using Trie Data Structure | 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. |
| 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 | – |
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 |
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.