Trie — Design Add and Search Words Data Structure
↗ LeetCode: Design Add and Search Words Data Structure · Medium · pattern chapter →
Asked atMetaAmazonGoogleUber
Design WordDictionary with addWord(word) and search(word). search may contain . which matches any letter.
Example —
WordDictionary w = new WordDictionary();
w.addWord("bad"); w.addWord("dad"); w.addWord("mad");
w.search("pad"); // false
w.search("bad"); // true
w.search(".ad"); // true
w.search("b.."); // trueConstraints — ≤ 25 chars/word; up to 10⁴ ops. Brute HashSet of words + brute-scan on wildcards — O(N·L) per wildcard search dies at 10⁵ queries. Trie + DFS for . wildcards is O(L·26^wildcards) per query — ~10⁶ ops even under load.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — HashSet + linear scan
search is O(N · L) worst — too slow with wildcards.
Approach 2 — Trie with DFS branching on . (canonical)
Insight. Standard trie for addWord. For search, DFS: at ., try all 26 children; else follow the single edge.
java
class WordDictionary {
class Node { Node[] c = new Node[26]; boolean end; }
Node root = new Node();
public void addWord(String w) {
Node cur = root;
for (char ch : w.toCharArray()) {
int i = ch - 'a';
if (cur.c[i] == null) cur.c[i] = new Node();
cur = cur.c[i];
}
cur.end = true;
}
public boolean search(String w) { return dfs(root, w, 0); }
boolean dfs(Node cur, String w, int idx) {
if (idx == w.length()) return cur.end;
char ch = w.charAt(idx);
if (ch == '.') {
for (Node child : cur.c) if (child != null && dfs(child, w, idx + 1)) return true;
return false;
}
int i = ch - 'a';
return cur.c[i] != null && dfs(cur.c[i], w, idx + 1);
}
}Execution Trace
Complexity — addWord O(L); search O(26^k · L) worst where k = # dots; usually much less.
Try it yourself
Complexity summary
| Approach | add | search | Grade |
|---|---|---|---|
| HashSet + scan | O(L) | O(N · L) | rejected |
| Trie + DFS | O(L) | O(26^k · L) | canonical |
When to use which
- Fixed alphabet + wildcards → trie + DFS branching.
- Long words → limit early via length check per branch.
- Regex support → NFA / recursive descent.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems