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.

Examples

Example 1:

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 <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of '.' or lowercase English letters.
  • There will be at most 10^4 calls to addWord and search.

Thinking Process

  1. Trie Foundation: Builds on standard Trie structure
  • DFS explores one branch fully before backtracking.
  • Mark visited nodes to avoid cycles on graphs.
  • Return aggregated results from children to the parent.
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};

class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    ~WordDictionary() {
        deleteTrie(root);
    }
    
    void addWord(string word) {
        TrieNode* node = root;
        for(char ch : word) {
            if(!node->children.contains(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isWord = true;
    }
    
    bool search(string word) {
        return searchInNode(word, 0, root);
    }

private:
    TrieNode* root;

    bool searchInNode(string& word, int idx, TrieNode* node) {
        if(!node) return false;
        if(idx == word.size()) return node->isWord;
        char curr = word[idx];
        if(curr == '.') {
            for(auto& [_, child]: node->children) {
                if(searchInNode(word, idx + 1, child)) {
                    return true;
                }
            }
            return false;
        }
        if(!node->children.contains(curr)) return false;
        return searchInNode(word, idx + 1, node->children[curr]);
    }

    void deleteTrie(TrieNode* node) {
        if(!node) return;
        for(auto& [_, child]: node->children) {
            deleteTrie(child);
        }
        delete node;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. Trie Foundation: Builds on standard Trie structure

How the code works:

  1. Trie Foundation: Builds on standard Trie structure
    • DFS explores one branch fully before backtracking.
    • Mark visited nodes to avoid cycles on graphs.
    • Return aggregated results from children to the parent.

      Common Mistakes

  2. Single wildcard: search(".") when no single-letter words exist
  3. All wildcards: search("...") explores all 3-letter words
  4. Wildcard at start: search(".ad") matches “bad”, “dad”, “mad”
  5. Wildcard at end: search("ba.") matches “bad”, “bat”, etc.
  6. No match: search("xyz") returns false correctly
  7. Empty word: Not applicable (constraints guarantee length ≥ 1)

  8. Multiple wildcards: search("b..") handles multiple wildcards

  9. Not handling null nodes: Forgetting to check if node exists before accessing
  10. Incorrect base case: Not checking idx == word.size() before checking isWord
  11. Wildcard logic: Not trying all children when encountering '.'
  12. Memory leaks: Forgetting to implement destructor
  13. Early exit: Not returning immediately when match found in wildcard search
  14. Index management: Off-by-one errors in recursive calls

When to Use This Structure

  1. Word Search with Wildcards: Pattern matching in dictionaries
  2. Autocomplete with Partial Input: When users type incomplete words
  3. Spell Checker: Finding similar words with wildcards
  4. Text Search: Searching documents with pattern matching
  5. Game Development: Word games like Scrabble, Boggle
  6. Search Engines: Prefix-based search with pattern support

This problem extends the Trie data structure with wildcard search capabilities. The key is using DFS to explore all possible paths when encountering wildcard characters, making it useful for pattern matching and flexible word search applications.

Key Takeaways

  1. Trie Foundation: Builds on standard Trie structure
  2. Wildcard Handling: DFS explores all paths when encountering '.'
  3. Early Termination: Returns true immediately when match found
  4. Memory Safety: Destructor prevents memory leaks
  5. Map vs Array: Using unordered_map is more flexible but slightly slower than array
  6. Recursive Search: Clean recursive approach for wildcard matching

References

Template Reference