Design Add and Search Words Data Structure

50.7k
0

Design a data structure that supports adding words and searching words later.

The search word may contain lowercase letters and the dot character ..

The dot . can match any one lowercase English letter.

Implement these operations:

  • addWord(word): Add a word into the data structure.

  • search(word): Return true if any previously added word matches the given pattern, otherwise return false.

Example 1

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

Output: false, true, true, true

Explanation: pad was never added, so it returns false. bad exists directly. .ad matches bad, dad, and mad. b.. matches bad.

Example 2

Input: addWord("cat"), addWord("cap"), search("ca."), search("c.t"), search("dog")

Output: true, true, false

Explanation: ca. matches both cat and cap. c.t matches cat. dog does not match any stored word.

Brute Force Approach

The most direct idea is to store the inserted words and, during search, compare the pattern against every possible candidate. One small observation makes this less wasteful: a pattern can only match words of the same length. That matters because b.. can never match badly, and .... can never match cat. So grouping words by length removes many useless comparisons immediately. After that, each search just checks whether at least one stored word of that exact length matches character by character, treating . as a free match.

Algorithm

  • Keep a map where the key is the word length and the value is a list of words having that length. This is done so search checks only realistic candidates.

  • In addWord, place the new word into the list for its length. This matters because future searches should find it only among words that can actually match.

  • In search, first look at the candidate list for the pattern length. If that length was never stored, return false immediately because no valid match can exist.

  • Compare the pattern with each candidate word character by character. This direct comparison is enough because both strings have the same length now.

  • If the current pattern character is a normal letter, it must match the candidate character exactly. If it is ., that position is accepted without comparison.

  • If every position matches for any one candidate word, return true immediately because the problem only asks whether a match exists.

  • If all candidate words fail, return false.

Dry Run

Design Add and Search Words Data Structure Brute Dry Run

Design Add and Search Words Data Structure Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class WordDictionary {
private:
unordered_map<int, vector<string>> groups;
// Checks whether one stored word matches the search pattern.
bool matchesPattern(const string& storedWord, const string& pattern) {
for (int i = 0; i < (int)pattern.length(); i++) {
// Normal letters must match exactly at the same position.
if (pattern[i] != '.' && pattern[i] != storedWord[i]) {
return false;
}
}
return true;
}
public:
// Adds one word to the group that has the same length.
void addWord(const string& word) {
// Store this word only with words that can match its future pattern length.
groups[(int)word.length()].push_back(word);
}
/*
Returns true if any stored word matches
the given pattern with dot wildcards.
*/
bool search(const string& pattern) {
// If this length was never added before, no match is possible.
if (groups.find((int)pattern.length()) == groups.end()) {
return false;
}
// Check only the words that have the same length as the pattern.
for (const string& storedWord : groups[(int)pattern.length()]) {
// Return early as soon as one valid match is found.
if (matchesPattern(storedWord, pattern)) {
return true;
}
}
return false;
}
};
// Driver code starts
int main() {
WordDictionary obj;
obj.addWord("bad");
obj.addWord("dad");
obj.addWord("mad");
cout << obj.search("pad") << endl;
cout << obj.search("bad") << endl;
cout << obj.search(".ad") << endl;
cout << obj.search("b..") << endl;
return 0;
}

Complexity Analysis

Time Complexity: addWord() takes O(L) average time apart from storing the string reference. search() takes O(K x L), where K is the number of stored words having the same length as the pattern and L is the pattern length.

Space Complexity: O(T), where T is the total number of characters across all stored words.

Optimal Approach

The key observation is that normal letters follow only one path in the dictionary, but . can branch into many possible paths. That matters because the data structure must support prefix-based movement very efficiently, and tries are built exactly for character-by-character movement. While adding a word, each character naturally moves deeper into the trie. During search, a normal letter means "go to exactly one child", but . means "try every child from here". That is why the search becomes a DFS problem on top of a trie.

Algorithm

  • Build a trie where every node stores 26 child links and one boolean telling whether a full word ends there. This structure is needed because words are matched one character at a time.

  • In addWord, start from the trie root and move through the characters of the word. Create a new child node whenever the required path does not exist yet.

  • After the last character is inserted, mark the final node as the end of a word. This matters because a full word match is different from just reaching some prefix.

  • In search, call a DFS helper with the pattern index and the current trie node. This helper is needed because wildcard search may branch into many choices.

  • If the current pattern character is a normal letter, move only to the matching child. If that child does not exist, return false immediately because this path cannot match.

  • If the current pattern character is ., try all existing children recursively. Return true as soon as one child leads to a full match.

  • When the full pattern is consumed, return whether the current node marks the end of a stored word. This final check is important because pattern length must match word length exactly.

Dry Run

Design Add and Search Word Data Structure Optimal Dry Run

Design Add and Search Word Data Structure Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class TrieNode {
public:
vector<TrieNode*> children;
bool isEndOfWord;
// Creates one trie node with empty child links.
TrieNode() {
// Reserve one child slot for each lowercase English letter.
children.assign(26, nullptr);
// This node does not mark a complete word yet.
isEndOfWord = false;
}
};
class WordDictionary {
private:
TrieNode* root;
// Tries to match the pattern from the current index and trie node.
bool dfs(const string& pattern, int index, TrieNode* node) {
// If the full pattern is consumed, only a complete stored word should pass.
if (index == (int)pattern.length()) {
return node->isEndOfWord;
}
// Take the current pattern character that controls the next move.
char ch = pattern[index];
// A normal letter must follow exactly one trie path.
if (ch != '.') {
TrieNode* nextNode = node->children[ch - 'a'];
// If that path does not exist, this pattern cannot match here.
if (nextNode == nullptr) {
return false;
}
return dfs(pattern, index + 1, nextNode);
}
// The dot can stand for any one letter, so try every possible child.
for (TrieNode* child : node->children) {
// Return early as soon as one branch gives a full match.
if (child != nullptr && dfs(pattern, index + 1, child)) {
return true;
}
}
return false;
}
public:
// Creates the root node of the trie.
WordDictionary() {
// All stored words start from this root.
root = new TrieNode();
}
// Adds one word into the trie.
void addWord(const string& word) {
// Start insertion from the root of the trie.
TrieNode* node = root;
for (char ch : word) {
// Convert the current character into a child index from 0 to 25.
int index = ch - 'a';
// Create a new node only when this path is used for the first time.
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
}
// Move to the next node for the next character.
node = node->children[index];
}
// Mark the final node so this full word can be matched later.
node->isEndOfWord = true;
}
/*
Returns true if any stored word matches
the given pattern with dot wildcards.
*/
bool search(const string& pattern) {
// Start wildcard search from the trie root and from index 0.
return dfs(pattern, 0, root);
}
};
// Driver code starts
int main() {
WordDictionary obj;
obj.addWord("bad");
obj.addWord("dad");
obj.addWord("mad");
cout << obj.search("pad") << endl;
cout << obj.search("bad") << endl;
cout << obj.search(".ad") << endl;
cout << obj.search("b..") << endl;
return 0;
}

Complexity Analysis

Time Complexity: addWord() takes O(L), where L is the word length. search() takes O(L) in simple cases without branching, but in the worst case with wildcards it can branch heavily, up to O(26D x L) where D is the number of dots.

Space Complexity: O(T), where T is the total number of stored characters in the trie.

Interview follow-up Questions

Words of different lengths can never match the same pattern, because . replaces exactly one character, not zero or many. So grouping by length removes many useless comparisons immediately.

TrieArraysData StructuresHashingStringSorting

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Comments0