Design Add and Search Words Data Structure

Problem Description

Design a data structure that supports adding new words and checking if a string matches any previously added word.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure.
• bool search(word) Returns true if there is any string in the data structure that matches word, where dots . can match any letter.

Examples

Constraints

• 1 ≤ word.length ≤ 25
• word in addWord consists of lowercase English letters.
• word in search consists of . or lowercase English letters.
• At most 10⁴ total calls will be made to addWord and search.

Branching Search Paths to Match Wildcards

A standard trie search traces a single path from root to child nodes. If you encounter a dot ., you cannot follow a single pointer. The dot can match any of the 26 possible child characters.

This means you must branch the search. When you hit a ., you iterate over all 26 possible child nodes at that level. For each valid child, you recursively search the remainder of the word. If any of these branches succeed, the search returns true. This turns a simple traversal into backtracking.

Solution 1: Trie with Backtracking Search

Implement a standard trie for word storage. For the search method, use a helper function that takes the current node and the index of the character to match, branching on dot wildcards.

class WordDictionary {
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
        }
        curr.isWord = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int index, TrieNode node) {
        if (node == null) return false;
        if (index == word.length()) return node.isWord;

        char c = word.charAt(index);
        if (c == '.') {
            // try all 26 possible branches
            for (TrieNode child : node.children) {
                if (child != null && dfs(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            int idx = c - 'a';
            return dfs(word, index + 1, node.children[idx]);
        }
    }
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.is_word = True

    def search(self, word: str) -> bool:
        def dfs(index, node):
            if index == len(word):
                return node.is_word

            c = word[index]
            if c == ".":
                # try all possible branches
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True
                return False
            else:
                if c not in node.children:
                    return False
                return dfs(index + 1, node.children[c])

        return dfs(0, self.root)

class WordDictionary {
private:
    struct TrieNode {
        TrieNode* children[26] = {};
        bool isWord = false;
    };
    TrieNode* root;

    bool dfs(const std::string& word, int index, TrieNode* node) {
        if (!node) return false;
        if (index == word.length()) return node->isWord;

        char c = word[index];
        if (c == '.') {
            // try all 26 possible branches
            for (int i = 0; i < 26; i++) {
                if (node->children[i] && dfs(word, index + 1, node->children[i])) {
                    return true;
                }
            }
            return false;
        } else {
            int idx = c - 'a';
            return dfs(word, index + 1, node->children[idx]);
        }
    }

public:
    WordDictionary() {
        root = new TrieNode();
    }

    void addWord(std::string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) {
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->isWord = true;
    }

    bool search(std::string word) {
        return dfs(word, 0, root);
    }
};

Complexity Analysis:

• Time Complexity:
  • addWord: O(L) where L is word length.
  • search: O(M) for words without wildcards, where M is word length. In the worst case (all dots .....), we may traverse up to O(26^L) nodes.
• Space Complexity: O(N * L) where N is the number of words. The helper recursion stack uses at most O(L) depth.

Where it breaks: If a search queries strings consisting entirely of wildcards . and the trie is heavily populated, the time complexity scales exponentially with length. In practice, the word length limit of 25 makes this manageable.

Why Not Store Words Grouped by Length in Hash Maps?

You can store words in hash maps grouped by their length. When searching, you only compare against words of the same length. While this is fast for simple cases, checking a wildcard against thousands of words requires linear scans of all words in that bucket, which degrades performance compared to the shared prefix compression in a trie.

Common Mistakes

• Not returning false when node is null. In backtracking, a branch can lead to a null pointer. You must guard against this immediately to prevent runtime errors.
• Forgetting that index == word.length() must return node.isWord. If you only return true at the end of the word, you will match prefixes rather than complete words.
• Re-allocating state objects inside search recursion. Keep parameters clean: pass index and node references directly to avoid memory thrashing.

Frequently Asked Questions

How does the time complexity change if we only search for exact matches? If there are no wildcard dots, the search functions exactly like a standard trie lookup, running in O(L) time.

What is the worst-case space complexity of the trie? O(N * L) where N is the total words inserted. Shared prefixes compress the space significantly compared to storing each string in isolation.

What does this problem test in interviews? It tests your ability to combine trie traversal with recursive depth-first search (DFS) and backtracking, which are essential for pattern matching engines.

← All Problems