211. Design Add and Search Words Data Structure

📝 Problem Details

• Title: 211. Design Add and Search Words Data Structure
• Link: https://leetcode.com/problems/design-add-and-search-words-data-structure/
• Difficulty: Medium
• Tags/Categories: Trie

💭What Were My Initial Thoughts?

- similar problem to Implement Trie (208)
- the wildcard "." means that the search function needs recursion or DFS
- a normal trie works for exact word searches, btu we need backtracking for wildcard searches

🤔What Did I Struggle With?

💡 Explanation of Solution

1. TrieNode Class (Helper Structure)

   • Each node stores:
     • children: a map of characters to child nodes.
     • isEnd: a flag to mark the end of a word.

2. Word Dictionary Class

   • addWord(word): Works like inserting into a Trie.
   • search(word):
     • If word has no wildcards, it’s a normal Trie search (O(n)).
     • If word contains '.', we use DFS (Depth-First Search) to explore all child nodes.
     • If '.' exists at some position, recursively try all possible characters at that level.

⌛ Complexity Analysis

Operation	Time Complexity	Space Complexity
Add Word	O(n)	O(n) (new nodes for each character)
Search (without .)	O(n)	O(1)
Search (with . wildcard)	O(26^n) worst case	O(1)

• The worst case for wildcard search (O(26^n)) happens when every character is '.' (full wildcard search).
• In practical cases, search is much faster due to pruning.

💻 Implementation of Solution

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd;
 
    TrieNode() {
        isEnd = false;
    }
};
 
class WordDictionary {
private:
    TrieNode* root;
 
public:
    WordDictionary() {
        root = new TrieNode();
    }
 
    // Add a word to the Trie
    void addWord(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }
 
    // Search for a word in the Trie, supporting '.' wildcard
    bool search(string word) {
        return searchInNode(word, 0, root);
    }
 
    // Helper function to perform DFS for the search
    bool searchInNode(const string& word, int index, TrieNode* node) {
        if (index == word.size()) {
            return node->isEnd;
        }
 
        char ch = word[index];
        if (ch == '.') {
            // If the character is '.', try all possible children
            for (auto& [key, childNode] : node->children) {
                if (searchInNode(word, index + 1, childNode)) {
                    return true;
                }
            }
            return false;
        } else {
            // If the character is a letter, proceed normally
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            return searchInNode(word, index + 1, node->children[ch]);
        }
    }
};