Design Add and Search Words Data Structure
Problem
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.
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.
add: bad, dad, mad; query: ".ad"trueclass 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]);
}
};Explanation
We store words in a trie — a tree where each edge is a letter, so shared prefixes share a path. Adding a word just walks letter by letter, creating child nodes as needed, and marks the final node with an end flag ("$") to say "a word stops here."
The interesting part is search with the wildcard .. A normal letter is easy: descend into that one specific child if it exists. But a . can be any letter, so at that position we must try every child and see if any branch leads to a match.
That branching is handled by a DFS over the trie. The recursion succeeds when we have consumed the whole query and the node we land on has its end flag set. For a . we recurse into all children and return true if any of them works.
Example: add bad, dad, mad, then query ".ad". The . tries the b, d, and m branches; following b then matching a and d reaches an end node, so the search returns true.
Adding is linear in the word length. A query with k dots can fan out across branches, which is where the worst-case 26^k factor comes from.