Design Add and Search Words Data Structure
Design a class WordDictionary with two methods. addWord(word) stores a lowercase word. search(word) returns true if any stored word matches word and false otherwise, where a '.' in word matches any one letter and every other letter must match exactly. A match has to cover a whole stored word of the same length, so after addWord("bad"), search("ba") is false.
Examples
addWord("bad"); addWord("dad"); addWord("mad"); search("pad"); search("bad") returns false, true
No stored word starts with "p", so "pad" fails. "bad" was added, so it matches letter for letter.
addWord("bad"); addWord("dad"); addWord("mad"); search(".ad"); search("b..") returns true, true
In ".ad" the dot can stand for b, d or m, and one match is enough. "b.." matches "bad" because each dot covers exactly one letter.
addWord("bad"); search("ba"); search("b..."); search("...") returns false, false, true
"ba" is only the start of "bad", not a whole stored word. "b..." needs four letters, while "..." matches "bad" because the lengths agree.
Constraints
- 1 <= word.length <= 25
- word in addWord consists of lowercase English letters.
- word in search consists of '.' or lowercase English letters.
- There will be at most 2 dots in word for search queries.
- At most 10^4 calls will be made to addWord and search.
Hints
Many stored words share their first letters. A structure that follows a word one letter at a time lets a lookup give up the moment no stored word continues.
Use a trie (prefix tree). For a '.', branch into every child with a recursive depth-first search.
addWord: walk or create one child per letter and mark the last node as a word end. search(i, node): if i == len(word), return node.end. If word[i] is '.', return true if any child succeeds at i + 1. Otherwise follow that letter's child if it exists, else return false.
Drill This: Your Approach First
Approach
Store the words in a trie where each node has up to 26 children and a flag marking the end of a word. addWord walks down, creating missing nodes. search walks the pattern recursively: a letter follows its one child, while a '.' tries every child and succeeds if any branch does. Reaching the end of the pattern counts only if that node's end flag is set. Here L is the word length, d the number of dots (at most 2) and T the total letters added.
Time
O(L) addWord, O(26^d * L) search
Space
O(T)
Pitfall
Solutions
class WordDictionary {
private static class Node {
Node[] children = new Node[26];
boolean end;
}
private final Node root = new Node();
public void addWord(String word) {
Node node = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) node.children[i] = new Node();
node = node.children[i];
}
node.end = true;
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String word, int i, Node node) {
if (i == word.length()) return node.end;
char c = word.charAt(i);
if (c == '.') {
for (Node child : node.children) {
if (child != null && dfs(word, i + 1, child)) return true;
}
return false;
}
Node child = node.children[c - 'a'];
return child != null && dfs(word, i + 1, child);
}
}class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.end = True
def search(self, word: str) -> bool:
def dfs(i: int, node: TrieNode) -> bool:
if i == len(word):
return node.end
c = word[i]
if c == ".":
return any(dfs(i + 1, child) for child in node.children.values())
if c not in node.children:
return False
return dfs(i + 1, node.children[c])
return dfs(0, self.root)