Log inSign up
mediumLeetCodeNot Started

Design Add and Search Words Data Structure

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

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 1 · Example 1: Dictionary with bad, dad, mad:

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: Trie structure: (root) / | \ b d m | | | a a a | | | d* d* d* search("pad") -> p not in root -> false. search("bad") -> follows b -> a -> d* -> true. search(".ad") -> root branches into b, d, m. All lead to "ad"* -> true. search("b..") -> follows b, then two . wildcards find a and d* -> 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 in typical tests (up to word length in general).
  • At most 104 calls will be made to addWord and search.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Extend a basic Trie with recursive depth-first search for wildcard resolution.
  • Understand the time-space trade-offs of branching on wildcard patterns.
  • Implement clean recursive backtracking on Trie nodes with index tracking.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Need to insert words and query prefix or pattern matches.
  • Query string contains wildcard characters like '.' matching any single character.
  • Exact word matching with isEnd termination flag.

Algorithmic Decision Tree:

  • Use a Trie where each node stores children[26] and boolean isEnd.
  • In search, pass the current node and character index into a recursive helper.
  • If word[idx] == '.', loop through all 26 children; if any returns true, return true immediately.

Connected Patterns:

Word Search IIRegular Expression MatchingPrefix and Suffix Search

1. List Storage with Character-by-Character Comparison

Intuition

Store words in vector<string>. On search(pattern), filter words of matching length and check if every char matches or is '.'. Return true on first match.

When to apply: Quick prototype when number of searches is tiny.

Algorithm

  1. Step 1: addWord(word): append word to wordsList.
  2. Step 2: search(word): loop through each w in wordsList.
  3. Step 3: If w.length() != word.length(), continue.
  4. Step 4: Check if word[k] == '.' || word[k] == w[k] for all characters.
  5. Step 5: If all match, return true. If loop completes, return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6class WordDictionary {
7 vector<string> words;
8public:
9 WordDictionary() {}
10
11 void addWord(string word) {
12 words.push_back(word);
13 }
14
15 bool search(string word) {
16 int len = word.length();
17 for (const string& w : words) {
18 if (w.length() != len) continue;
19 bool match = true;
20 for (int i = 0; i < len; i++) {
21 if (word[i] != '.' && word[i] != w[i]) {
22 match = false;
23 break;
24 }
25 }
26 if (match) return true;
27 }
28 return false;
29 }
30};
31
32int main() {
33 WordDictionary dict;
34 dict.addWord("bad");
35 dict.addWord("dad");
36 dict.addWord("mad");
37 cout << "search(\"pad\"): " << (dict.search("pad") ? "true" : "false") << endl;
38 cout << "search(\"bad\"): " << (dict.search("bad") ? "true" : "false") << endl;
39 cout << "search(".ad"): " << (dict.search(".ad") ? "true" : "false") << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: addWord: O(1), search: O(N * L) — Must iterate up to N words and perform L character comparisons each.
  • Space complexity: O(N * L) — Stores all N words of length L.

Why Brute Force Doesn't Scale:

With 10,000 words and 10,000 search calls, brute force performs 108 string operations, timing out.

Trie reduces non-wildcard queries to O(L) <= 25 steps, answering queries in microseconds.

2. Length-Bucketed Hash Map

Intuition

Maintain unordered_map<int, vector<string>>. On search, only retrieve candidates from map[word.length()], skipping all words of differing lengths.

When to apply: Intermediate optimization reducing comparisons when words have diverse lengths.

Algorithm

  1. Step 1: Map word length -> vector of words.
  2. Step 2: In addWord, bucket[word.length()].push_back(word).
  3. Step 3: In search, if length not in bucket, return false immediately.
  4. Step 4: Scan only the bucket of matching length.
  5. Step 5: Return true if any word matches.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5using namespace std;
6
7class WordDictionary {
8 unordered_map<int, vector<string>> lengthBuckets;
9public:
10 WordDictionary() {}
11
12 void addWord(string word) {
13 lengthBuckets[word.length()].push_back(word);
14 }
15
16 bool search(string word) {
17 int len = word.length();
18 if (lengthBuckets.find(len) == lengthBuckets.end()) return false;
19 for (const string& w : lengthBuckets[len]) {
20 bool match = true;
21 for (int i = 0; i < len; i++) {
22 if (word[i] != '.' && word[i] != w[i]) {
23 match = false;
24 break;
25 }
26 }
27 if (match) return true;
28 }
29 return false;
30 }
31};
32
33int main() {
34 WordDictionary dict;
35 dict.addWord("bad");
36 dict.addWord("dad");
37 cout << "search(".ad"): " << (dict.search(".ad") ? "true" : "false") << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: addWord: O(1), search: O(K * L) — K is the number of words having the query length. In the worst case K = N.
  • Space complexity: O(N * L) — Stores words in length buckets.

3. Trie with Recursive Backtracking on Wildcards

Intuition

Insertion runs in linear time O(L) inserting into the Trie. For search, traverse recursively. If the char is a letter, advance to node.children[char - 'a']. If the char is '.'. iterate over all 26 children; if any sub-branch returns true, return true immediately.

When to apply: Standard optimal design required in production systems and interview standards.

Algorithm

  1. Step 1: TrieNode contains children[26] and isEnd boolean flag.
  2. Step 2: addWord(word) walks Trie inserting characters and sets isEnd = true at the final node.
  3. Step 3: search(word) invokes dfs(root, word, 0).
  4. Step 4: Base case: if index == word.length(), return node.isEnd.
  5. Step 5: If word[index] != '.': if node.children[word[index] - 'a'] is null return false, else recurse.
  6. Step 6: If word[index] == '.': iterate child 0..25. If non-null and dfs(child, word, index + 1) is true, return true.
  7. Step 7: Return false if no branch succeeds.

Interactive Wildcard Search Trace for '.ad'

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: search('
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'b'
'b'
char 'd'
'd'

Node order shown; add connections to display explicit tree edges.

wildcard: b
Check / comparison
word[0] == '.' -> branch to children['b']
Decision / next transition
Recurse on node 'b' with idx = 1.
Why this step matters

Step 1: search(.ad, idx=0) at root. Character is .. Iterate children: child b is non-null. Branch into child b.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 bool isEnd;
9 TrieNode() : isEnd(false) {
10 for (int i = 0; i < 26; i++) children[i] = nullptr;
11 }
12};
13
14class WordDictionary {
15 TrieNode* root;
16
17 bool dfs(TrieNode* node, const string& word, int idx) {
18 if (!node) return false;
19 if (idx == word.length()) return node->isEnd;
20
21 char c = word[idx];
22 if (c != '.') {
23 int childIdx = c - 'a';
24 return dfs(node->children[childIdx], word, idx + 1);
25 } else {
26 for (int i = 0; i < 26; i++) {
27 if (node->children[i] && dfs(node->children[i], word, idx + 1)) {
28 return true;
29 }
30 }
31 return false;
32 }
33 }
34
35public:
36 WordDictionary() {
37 root = new TrieNode();
38 }
39
40 void addWord(string word) {
41 TrieNode* curr = root;
42 for (char c : word) {
43 int idx = c - 'a';
44 if (!curr->children[idx]) {
45 curr->children[idx] = new TrieNode();
46 }
47 curr = curr->children[idx];
48 }
49 curr->isEnd = true;
50 }
51
52 bool search(string word) {
53 return dfs(root, word, 0);
54 }
55};
56
57int main() {
58 WordDictionary dict;
59 dict.addWord("bad");
60 dict.addWord("dad");
61 dict.addWord("mad");
62 cout << "Optimal search(\"pad\"): " << (dict.search("pad") ? "true" : "false") << endl;
63 cout << "Optimal search(\"bad\"): " << (dict.search("bad") ? "true" : "false") << endl;
64 cout << "Optimal search(".ad"): " << (dict.search(".ad") ? "true" : "false") << endl;
65 cout << "Optimal search(\"b..\"): " << (dict.search("b..") ? "true" : "false") << endl;
66 return 0;
67}

Time & Space Complexity

  • Time complexity: addWord: O(L), search: O(L) best, O(26^D * L) worst — D is the number of dots. When D=0, search is strictly O(L). With D dots, branches at most 26D times.
  • Space complexity: O(Total chars * 26) — Trie nodes store 26 pointers each. Depth of recursion is bounded by word length L <= 25.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — List of Strings with Regex MatchaddWord: O(1), search: O(N * L)O(N * L)Store words in a dynamic array. For search, iterate through all N stored words and compare character by character.Iterating every word on every search.
2.Better — Hash Map Grouped by Word LengthaddWord: O(1), search: O(K * L)O(N * L)Group words in a hash map unordered_map<int, vector<string>> keyed by length.Linear scan across words of identical length.
3.Optimal — Trie with Recursive DFS for WildcardsOptimaladdWord: O(L), search: O(L) best, O(26^D * L) worstO(Sum of word lengths * 26)Standard Trie insertion. For search, recurse on Trie: standard characters take O(1) transition, while '.' checks all non-null children.Branching factor on wildcard dots.

Common Pitfalls & Crucial Edge Cases

Forgetting `node.isEnd` check

Returning true just because all characters were matched without checking if the node is a complete word.

Not pruning early on wildcard

Waiting for all 26 branches to finish instead of returning true as soon as the first branch succeeds.

Re-creating recursive arrays/substrings

Passing sliced strings word.substring(1) on each recursive call creates O(L2) garbage instead of passing index idx.

Crucial Edge Cases to Validate:

  • Search word entirely made of dots ('...') — Explores all Trie paths up to depth 3 to check if any 3-letter word exists.
  • Search word longer than any stored word — Returns false gracefully when Trie height is exceeded.
  • Single character word with dot ('.') — Tests if any 1-letter word has isEnd = true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explicitly mention using idx parameter instead of string slicing to keep space complexity minimal.
  2. Discuss worst-case performance when words have many dots vs typical case.
  3. Highlight how Trie memory scales linearly with word characters thanks to shared prefixes.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the worst-case time complexity of search when a query contains D wildcard dots in a word of length L?

2.Why is an index integer passed to the recursive dfs function instead of slicing the string?

Back to DSA Sheet