Design Add and Search Words Data Structure

Problem

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.

Example:

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:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

Constraints:

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

Solution

Approach: Trie with Wildcard DFS

The key insight is to use a trie like before, but for search with wildcards, we use DFS to explore all possible branches when encountering a dot.

Implementation

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

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

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

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

            char = word[i]

            if char == '.':
                # Try all possible children
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            else:
                # Regular character match
                if char not in node.children:
                    return False
                return dfs(node.children[char], i + 1)

        return dfs(self.root, 0)

Complexity Analysis

Time Complexity:
- addWord: O(m), where m is the length of the word
- search: O(m) for words without dots, O(26^d * m) in worst case where d is the number of dots
Space Complexity: O(n * m), where n is the number of words and m is average word length.

Key Insights

Wildcard Handling: A dot can match any character, so we must explore all possible branches at that position using DFS.
Backtracking Pattern: When we hit a dot, we try each child and backtrack if it doesn’t lead to a match.
Regular Characters: Non-dot characters work exactly like the standard trie - follow the specific child or return false.
DFS with Index: We pass the current position in the word as a parameter, making it easy to check if we’ve consumed the entire word.
Early Termination: If any branch returns true, we can immediately return true without exploring other branches.