#211
Design Add and Search Words Data Structure
Medium Trie + DFS for wildcards
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Support addWord(word) and search(pattern), where '.' in the pattern matches any one letter.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: search where '.' matches any letter.
Why this works: same trie; on '.', try every child (a small DFS).
Example: add "bad", "dad"
search ".ad" → try b, d, … → "bad" ✓ → true✦Hints open one at a time
Store words in a trie.
For '.', try every existing child — that's a DFS.
↗Approach
Same trie as before. search(pattern, i, node): at the end return node.end; for a letter go to that child; for '.', return true if any child succeeds.
</>Solution (Java)
class WordDictionary {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
public void addWord(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
}
cur.end = true;
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String w, int i, Node node) {
if (node == null) return false;
if (i == w.length()) return node.end;
char c = w.charAt(i);
if (c != '.') return dfs(w, i + 1, node.next[c - 'a']);
for (Node child : node.next) { // '.' tries every branch
if (dfs(w, i + 1, child)) return true;
}
return false;
}
}!Common mistake
Storing words in a list and regex-matching each one on every search.
Complexity
- Time: O(L) to add; search is O(L) without dots, up to O(26^d · L) with d dots.
- Space: O(total characters).
Topic: Trie
🎬 Episode 97: video coming soon