Design Add and Search Words Data Structure

MediumTries

Design a structure that adds words and searches them, where a search query may contain '.' matching any single letter.

Constraints

1 <= word.length <= 25
Search words may contain dots

Trie with wildcard DFS

Time O(n) typical, O(26^n) worst with many dotsSpace O(total characters)

Store words in a trie. For a normal letter, follow the single child; for '.', recurse into every child. A match requires reaching an end-of-word node after the last character.

#include <bits/stdc++.h>
using namespace std;

class WordDictionary {
    struct Node { Node* next[26] = {}; bool end = false; };
    Node* root = new Node();
public:
    void addWord(string word) {
        Node* cur = root;
        for (char c : word) {
            if (!cur->next[c - 'a']) cur->next[c - 'a'] = new Node();
            cur = cur->next[c - 'a'];
        }
        cur->end = true;
    }
    bool search(string word) { return dfs(word, 0, root); }
private:
    bool dfs(const string& w, int i, Node* node) {
        if (!node) return false;
        if (i == (int)w.size()) return node->end;
        if (w[i] == '.') {
            for (int c = 0; c < 26; c++)
                if (dfs(w, i + 1, node->next[c])) return true;
            return false;
        }
        return dfs(w, i + 1, node->next[w[i] - 'a']);
    }
};