Design add and Search Word

211.Design Add and Search Words Data Structure

Trie

Design

Depth-First Search

String

Problem Statement:

Design a data structure that supports adding new words and finding if a string matches any added string. String matching supports '.' as a wildcard that can match any letter.

Example:

Input:

["WordDictionary","addWord","search"]
[[],["bad"],["b.d"]]

→

Output:

[null,null,true]

Algorithm:

1. Use Trie structure to store words
2. Regular insert for addWord
3. DFS with backtracking for search
4. Handle wildcards by trying all children

Complexity:

AddWord: O(m) | Search: O(m) for exact, O(26^m) for all wildcards
where m is word length

Java Solution:

class WordDictionary {
    TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode curr = root;
        
        // Standard trie insertion
        for (char c : word.toCharArray()) {
            curr.map.putIfAbsent(c, new TrieNode());
            curr = curr.map.get(c);
        }
        
        curr.isWord = true;
    }
    
    public boolean search(String word) {
        return dfs(word, 0, root);
    }
    
    private boolean dfs(String word, int index, TrieNode node) {
        // Base case: reached end of word
        if (index == word.length()) {
            return node.isWord;
        }
        
        char c = word.charAt(index);
        
        if (c == '.') {
            // Try all possible children for wildcard
            for (TrieNode child : node.map.values()) {
                if (dfs(word, index + 1, child)) 
                    return true;
            }
            return false;
        } else {
            // Normal character matching
            TrieNode nextNode = node.map.get(c);
            if (nextNode == null) return false;
            return dfs(word, index + 1, nextNode);
        }
    }
    
    // TrieNode definition
    class TrieNode {
        boolean isWord;
        Map<Character, TrieNode> map;
        
        public TrieNode() {
            this.isWord = false;
            this.map = new HashMap<>();
        }
    }
}

Python Solution:

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(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_word
            
            if word[i] == '.':
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            
            if word[i] not in node.children:
                return False
                
            return dfs(node.children[word[i]], i + 1)
        
        return dfs(self.root, 0)

C++ Solution:

class WordDictionary {
private:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isWord = false;
    };
    
    TrieNode* root;
    
    bool dfs(string& word, int index, TrieNode* node) {
        if (index == word.length())
            return node->isWord;
            
        char c = word[index];
        if (c == '.') {
            for (auto& [ch, child] : node->children) {
                if (dfs(word, index + 1, child))
                    return true;
            }
            return false;
        } else {
            if (!node->children.count(c))
                return false;
            return dfs(word, index + 1, node->children[c]);
        }
    }
    
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (!curr->children.count(c))
                curr->children[c] = new TrieNode();
            curr = curr->children[c];
        }
        curr->isWord = true;
    }
    
    bool search(string word) {
        return dfs(word, 0, root);
    }
};