Design Add and Search Words Data Structure

Design a data structure that supports adding new words and searching for existing words.

Implement the WordDictionary class:

• 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 or false otherwise. word may contain dots '.' where dots can be matched with any letter.

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("day");
wordDictionary.addWord("bay");
wordDictionary.addWord("may");
wordDictionary.search("say"); // return false
wordDictionary.search("day"); // return true
wordDictionary.search(".ay"); // return true
wordDictionary.search("b.."); // return true

Approach

Use a trie to store words. For addWord, insert characters normally. For search, perform DFS: when the current character is a dot, try all child edges; otherwise follow the matching edge. This supports up to two dots efficiently given the constraints.

Why It Works

A trie represents all inserted words as root-to-leaf paths. The DFS explores exactly the paths consistent with the search pattern (treating dots as wildcards). If any path reaches a node marked as a word end at the pattern length, the search should return true.

Complexity

• Time: O(L) for add, O(L) average for search, worst-case O(26^L) with many dots
• Space: O(total characters) for the trie

Reference Implementation (Python)

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

class WordDictionary:

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

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

    def search(self, word: str) -> bool:
        def dfs(index: int, node: TrieNode) -> bool:
            if index == len(word):
                return node.end
            ch = word[index]
            if ch == '.':
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True
                return False
            if ch not in node.children:
                return False
            return dfs(index + 1, node.children[ch])

        return dfs(0, self.root)