Design a data structure that supports addWord and search where search can use . as a wildcard matching any letter.
addWord("bad"), addWord("dad"), search("pad")→false, search(".ad")→true, search("b..")→true
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.
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)