Design Add and Search Words Data Structure

Practice Link

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.

Intuition#

This is a plain Trie (like Implement Trie) with one twist — search supports a wildcard . that can match any single character.

• addWord is identical to a normal trie insert: walk/create a node per character, mark the last node as isEnd.
• search can't be a simple iterative walk anymore, because a . doesn't point to one child — it could match any of the 26. So the moment we see a ., we branch into every existing child and check if any of them lead to a match.

That branching is what forces recursion (DFS) instead of a loop: isFound(node, word, idx) tries to match word[idx..] starting at node.

• Base case: idx == word.size() → we've consumed the whole word, so the match is valid only if node->isEnd is true.
• If node is NULL, that path is dead — return false.
• If word[idx] is a normal letter, follow the single matching child.
• If word[idx] is ., try all 26 children; return true if any of them succeeds.

Worst case (lots of dots) this degenerates into exploring a large chunk of the trie, but in practice it prunes fast since most branches go NULL quickly.

Solution#

class TrieNode{
public:
    bool isEnd;
    TrieNode* children[26];

    TrieNode(){
        isEnd = false;
        for(int i=0;i<26;i++){
            children[i] = NULL;
        }
    }
};

class WordDictionary {
public:
    TrieNode* root;
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* curr = root;
        for(char c: word){
            int idx = c - 'a';

            if(curr->children[idx] == NULL){
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->isEnd = true;
    }

    bool isFound(TrieNode * node, string word, int idx){
        if(!node)
            return false;

        if(idx == word.size()){
            return node->isEnd;
        }

        if(word[idx] != '.'){
            return isFound(node->children[word[idx] - 'a'], word, idx+1);
        }else{
            for(int i=0;i<26;i++){
                if(isFound(node->children[i], word, idx+1))
                    return true;
            }
            return false;
        }
    }
    
    bool search(string word) {
        return isFound(root, word, 0);
    }
};

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

Complexities#

Let m = length of word, n = number of words stored, alphabet = 26.

Time Complexity:

• addWord: O(m)
• search: O(m) when no dots, up to O(alphabet^m) in the worst case (e.g. ".....") since every dot can branch into 26 recursive calls.

Space Complexity: O(n × m) for the trie storage, plus O(m) recursion stack depth per search call.