Design Add and Search Words Data Structure

Design a data structure that supports addWord and search where search can use . as a wildcard matching any letter.

Example 1

addWord("bad"), addWord("dad"), search("pad")→false, search(".ad")→true, search("b..")→true

Solution Approach

Trie with DFS for wildcard: when . encountered, try all 26 children recursively.

Trie with TrieNode (children[26], isEnd).
addWord: standard Trie insert.
search: DFS; at each non-dot char, go to specific child; at dot, try all children.
Return isEnd when all chars processed.

Java

class WordDictionary {
    private TrieNode root = new TrieNode();

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.ch[c-'a'] == null) node.ch[c-'a'] = new TrieNode();
            node = node.ch[c-'a'];
        }
        node.end = true;
    }
    public boolean search(String word) { return dfs(root, word, 0); }
    private boolean dfs(TrieNode node, String word, int i) {
        if (i == word.length()) return node.end;
        char c = word.charAt(i);
        if (c != '.') {
            return node.ch[c-'a'] != null && dfs(node.ch[c-'a'], word, i+1);
        }
        for (TrieNode child : node.ch) if (child != null && dfs(child, word, i+1)) return true;
        return false;
    }
    private static class TrieNode { TrieNode[] ch = new TrieNode[26]; boolean end; }
}

Time Complexity: addWord: O(L); search: O(L * 26^k) where k is number of dots
Space Complexity: O(N*L)