LeetCode Solution 211 - Design Add and Search Words Data Structure

Problem Statement

Design a data structure that supports adding new words and finding words even if they contain ‘.’ as a wildcard character.

Implement the WordDictionary class:

• void addWord(word): Adds a word into the data structure.
• bool search(word): Returns true if the word is in the data structure, otherwise returns false. The word may contain . where . can match any letter.

Example

Input:

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // Returns false
wordDictionary.search("bad"); // Returns true
wordDictionary.search(".ad"); // Returns true
wordDictionary.search("b.."); // Returns true

---

Optimal Approach: Trie with DFS (Backtracking)

The most efficient way to solve this problem is by using a Trie (Prefix Tree) combined with Depth-First Search (DFS) for wildcard searches.

Algorithm Steps:

1. Insertion (addWord):
   • Traverse the Trie and create new nodes if needed.
   • Mark the last node as the end of a word.
2. Search (search):
   • Traverse the Trie normally for non-wildcard characters.
   • For . wildcard, recursively search all possible child nodes.

---

LeetCode-Compatible C++ Solution

class WordDictionary {
private:
    struct TrieNode {
        bool isEnd;
        TrieNode* children[26];
        TrieNode() {
            isEnd = false;
            fill(begin(children), end(children), nullptr);
        }
    };
    TrieNode* root;

    bool searchHelper(const string &word, int index, TrieNode* node) {
        if (!node) return false;
        if (index == word.size()) return node->isEnd;

        char c = word[index];
        if (c == '.') {
            for (TrieNode* child : node->children) {
                if (child && searchHelper(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            int i = c - 'a';
            return searchHelper(word, index + 1, node->children[i]);
        }
    }

public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (!node->children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        return searchHelper(word, 0, root);
    }
};

---

Step-by-Step Explanation

1. Node Structure: Each node stores children (26 letters) and an isEnd flag.
2. Insertion: Traverse existing nodes or create new ones.
3. Search:
   • If a normal character, follow the Trie path.
   • If . wildcard, recursively explore all children.

---

Dry Run with Sample Input

Given Input:

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

Execution:

Operation	Trie Structure	Output
Insert "bad"	root → b → a → d (end)	-
Insert "dad"	root → d → a → d (end)	-
Insert "mad"	root → m → a → d (end)	-
Search "pad"	Not found	❌ False
Search "bad"	Found	✅ True
Search ".ad"	Matches "bad", "dad", "mad"	✅ True
Search "b.."	Matches "bad"	✅ True

---

Alternative Approaches

1. Using HashMap (Trie Alternative)

• Time Complexity: O(N) for each operation.
• Space Complexity: O(N × 26) for storing all words.
• Why Not? Still a Trie-based approach, but using unordered_map instead of arrays.

2. Using Set Data Structure

• Idea: Store all words in a unordered_set<string>.
• Time Complexity: O(1) for exact search, O(N) for wildcard search.
• Why Not? Takes extra space and inefficient for wildcard matching.

3. Brute Force (Linear Search in List of Words)

• Time Complexity: O(N) per query.
• Space Complexity: O(N).
• Why Not? Slow for large datasets.

---

Best Solution: Trie with DFS

Approach	Time Complexity	Space Complexity	Efficiency
Brute Force	O(N) per search	O(N)	❌ Slow
HashMap-Based Trie	O(N) per op	O(N × 26)	❌ Extra Space
Trie + DFS	O(N) per op	O(N × 26)	✅ Best

The Trie + DFS solution is the best approach as it efficiently handles wildcard searches in O(N) time.

---

Conclusion

The Trie Data Structure with DFS is the optimal approach for solving the Design Add and Search Words Data Structure problem, providing efficient insert and search operations in O(N) time.

Similar Problems for Practice:

1. Implement Trie (Prefix Tree)
2. Replace Words
3. Word Search II

This problem demonstrates the power of Trie structures combined with DFS backtracking for wildcard searches.