Medium

Design Add and Search Words Data Structure

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.

Examples

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]

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.

Trie with DFS for Dot Wildcards

Approach

Adding words is identical to standard Trie insertion. For searching, if we encounter a regular character, we traverse the child node as usual. If we encounter a '.' wildcard, we must explore ALL possible child nodes. We can use a recursive Depth-First Search (DFS) helper function. If `dfs` returns true for any child path, we return true. If we reach the end of the word, we check `isEndOfWord`.

Complexity Analysis

Time Complexity

O(m) add, O(26^m) worst-case search

Space Complexity

O(m * N)

Due to the wildcard '.', search can potentially branch to all 26 children at each step, though in practice it is constrained by existing paths.

Solution.java

1class TrieNode {2    TrieNode[] children;3    boolean isEndOfWord;4    5    public TrieNode() {6        children = new TrieNode[26];7        isEndOfWord = false;8    }9}10
11class WordDictionary {12    private TrieNode root;13
14    public WordDictionary() {15        root = new TrieNode();16    }17    18    public void addWord(String word) {19        TrieNode curr = root;20        for (char c : word.toCharArray()) {21            int index = c - 'a';22            if (curr.children[index] == null) {23                curr.children[index] = new TrieNode();24            }25            curr = curr.children[index];26        }27        curr.isEndOfWord = true;28    }29    30    public boolean search(String word) {31        return dfs(word, 0, root);32    }33    34    private boolean dfs(String word, int index, TrieNode node) {35        if (index == word.length()) {36            return node.isEndOfWord;37        }38        39        char c = word.charAt(index);40        41        if (c == '.') {42            // Explore all possible children43            for (int i = 0; i < 26; i++) {44                if (node.children[i] != null && dfs(word, index + 1, node.children[i])) {45                    return true;46                }47            }48            return false;49        } else {50            // Standard search51            int childIndex = c - 'a';52            if (node.children[childIndex] == null) {53                return false;54            }55            return dfs(word, index + 1, node.children[childIndex]);56        }57    }58}