Problem statement

Design a word collection that can answer pattern queries in which a dot matches any single letter. Write the class WordDictionary:

• WordDictionary() creates an empty collection.
• void addWord(String word) adds word.
• boolean search(String word) returns true if some added word matches word, false otherwise. word may contain dots '.'; a dot matches any one letter. A match must have exactly the same length.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

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: "pad" was never added. ".ad" matches bad, dad and mad; "b.." matches bad.

Example 2

Input: ["WordDictionary","search","addWord","addWord","search","search","search"]
[[],["."],["a"],["ab"],["."],[".."],["a.c"]]
Output: [null,false,null,null,true,true,false]
Explanation: An empty collection matches nothing. "." matches the one-letter word "a" and ".." matches "ab"; no three-letter word was added.

Constraints

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters
• word in search consists of lowercase letters and '.'
• There are at most 2 dots in word for search queries
• At most 10^4 calls are made to addWord and search

Hints for Design Add and Search Words Data Structure

1. Hint 1

   Without dots this is exactly a trie lookup.

2. Hint 2

   A dot does not tell you which child to follow — so try all of them.

3. Hint 3

   Search recursively: at position i with node n, a letter follows one child, a dot tries every existing child; at the end of the pattern, succeed only if n marks a word end.

How to solve Design Add and Search Words Data Structure

Store the words in a trie. A pattern lookup walks the trie like a normal search, except that at a dot it branches into every child — a depth-first search that succeeds as soon as one branch reaches a word end exactly at the pattern's end.

Approach

1. addWord(word): insert into the trie, marking the last node as a word end.
2. search(word): call dfs(root, 0).
3. dfs(node, i): if i == word.length return whether node is a word end. If word[i] is a letter, recurse into that child if it exists (else fail). If it is a dot, return true if dfs(child, i + 1) succeeds for any child.

Why it works

A word matches the pattern exactly when its trie path agrees with every letter of the pattern and has the same length. The search explores exactly those paths: it follows the forced child for a letter, every child for a dot, and checks the end flag when the pattern runs out, so it finds a match if and only if one was added.

Complexity

• Time — O(L) per addWord; O(26^d · L) per search with d dots (d <= 2 here)
• Space — O(total letters added)

Pitfalls

• A match must end at a node marked as a word end — "ba." must not match a stored "bad" prefix of "badge" unless "bad" itself was added.
• Return early once a branch succeeds; exploring the remaining children is wasted work.

Reference solution

Python

class WordDictionary:

    def __init__(self):
        self.root = {}  # letter -> child node; "$" marks a word end

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return "$" in node
            ch = word[i]
            if ch == ".":
                return any(dfs(child, i + 1) for key, child in node.items() if key != "$")
            child = node.get(ch)
            return child is not None and dfs(child, i + 1)
        return dfs(self.root, 0)

Java

class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    private Node root = new Node();

    public WordDictionary() {
    }

    public void addWord(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.next[c] == null) node.next[c] = new Node();
            node = node.next[c];
        }
        node.end = true;
    }

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

    private boolean dfs(Node node, String word, int i) {
        if (i == word.length()) return node.end;
        char ch = word.charAt(i);
        if (ch != '.') {
            Node child = node.next[ch - 'a'];
            return child != null && dfs(child, word, i + 1);
        }
        for (Node child : node.next) if (child != null && dfs(child, word, i + 1)) return true;
        return false;
    }
}

C++

class WordDictionary {
    struct Node {
        Node* next[26] = {};
        bool end = false;
    };
    Node* root = new Node();

    bool dfs(Node* node, const string& word, size_t i) {
        if (i == word.size()) return node->end;
        if (word[i] != '.') {
            Node* child = node->next[word[i] - 'a'];
            return child && dfs(child, word, i + 1);
        }
        for (Node* child : node->next) if (child && dfs(child, word, i + 1)) return true;
        return false;
    }
public:
    WordDictionary() {}

    void addWord(string word) {
        Node* node = root;
        for (char ch : word) {
            int c = ch - 'a';
            if (!node->next[c]) node->next[c] = new Node();
            node = node->next[c];
        }
        node->end = true;
    }

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

JavaScript

var WordDictionary = function() {
    this.root = { children: {}, end: false };
};

WordDictionary.prototype.addWord = function(word) {
    var node = this.root;
    for (var i = 0; i < word.length; i++) {
        var ch = word[i];
        if (!node.children[ch]) node.children[ch] = { children: {}, end: false };
        node = node.children[ch];
    }
    node.end = true;
};

WordDictionary.prototype.search = function(word) {
    var dfs = function(node, i) {
        if (i === word.length) return node.end;
        var ch = word[i];
        if (ch !== ".") return !!node.children[ch] && dfs(node.children[ch], i + 1);
        for (var k in node.children) if (dfs(node.children[k], i + 1)) return true;
        return false;
    };
    return dfs(this.root, 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium