Word Dictionary With Wildcard Search
Problem
Design a class that supports addWord(w) and search(q). The query may contain '.' which matches any single letter. Return true iff some inserted word matches the query in full.
Store words in a trie. For a regular character, descend into that one child if it exists. For '.', recurse into every existing child. The search succeeds if any branch lands on a node whose end flag is set after the last character.
Input
add: bad, dad, mad; query: ".ad"Output
true'.' matches b, d, or m — any of bad, dad, mad satisfies the query.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, w):
node = self.root
for c in w:
node = node.setdefault(c, {})
node["$"] = True
def search(self, q):
def dfs(i, node):
if i == len(q): return "$" in node
c = q[i]
if c == ".":
return any(dfs(i + 1, ch) for k, ch in node.items() if k != "$")
return c in node and dfs(i + 1, node[c])
return dfs(0, self.root)class WordDictionary {
constructor() { this.root = {}; }
addWord(w) {
let n = this.root;
for (const c of w) n = n[c] || (n[c] = {});
n.$ = true;
}
search(q) {
const dfs = (i, n) => {
if (i === q.length) return n.$ === true;
const c = q[i];
if (c === ".") {
for (const k of Object.keys(n)) if (k !== "$" && dfs(i + 1, n[k])) return true;
return false;
}
return n[c] && dfs(i + 1, n[c]);
};
return dfs(0, this.root);
}
}class WordDictionary {
static class Node { Map<Character, Node> ch = new HashMap<>(); boolean end; }
Node root = new Node();
public void addWord(String w) {
Node n = root;
for (char c : w.toCharArray()) n = n.ch.computeIfAbsent(c, k -> new Node());
n.end = true;
}
public boolean search(String q) { return dfs(0, q, root); }
boolean dfs(int i, String q, Node n) {
if (i == q.length()) return n.end;
char c = q.charAt(i);
if (c == '.') {
for (Node ch : n.ch.values()) if (dfs(i + 1, q, ch)) return true;
return false;
}
Node nx = n.ch.get(c);
return nx != null && dfs(i + 1, q, nx);
}
}struct Node { unordered_map<char, Node*> ch; bool end = false; };
class WordDictionary {
Node* root = new Node();
public:
void addWord(string w) {
Node* n = root;
for (char c : w) {
if (!n->ch.count(c)) n->ch[c] = new Node();
n = n->ch[c];
}
n->end = true;
}
bool search(string q) { return dfs(0, q, root); }
bool dfs(int i, string& q, Node* n) {
if (i == (int)q.size()) return n->end;
char c = q[i];
if (c == '.') {
for (auto& [k, v] : n->ch) if (dfs(i + 1, q, v)) return true;
return false;
}
return n->ch.count(c) && dfs(i + 1, q, n->ch[c]);
}
};