Design Add And Search Words Data Structure
The drill: A word set with a wildcard twist — add words, then ask whether a query matches one, where a dot in the query stands for exactly one unknown letter. The query's length still has to match a stored word's length exactly.
Build a word store with a wildcard twist on lookup: add words one at a time, then answer whether a query string matches some added word, where a dot character in the query stands for exactly one unknown letter.
A match requires the query and the stored word to be the same length — a dot fills in for one letter, it never stands for zero letters or more than one — and every non-dot character in the query must match the stored word exactly at that position.
Multiple dots can appear in the same query, each one independently free to match any letter, as long as some single stored word satisfies every position at once.
- words and queries contain lowercase letters and, in queries only, the dot wildcard
- a dot in the query matches exactly one letter, never more or fewer
- a match requires the query length to equal the stored word's length
- the same word may be added more than once without effect
HINT 1 THE NUDGE
A dot has to match any single letter — comparing whole strings against every stored word works, but rescans the entire set every time, dot or no dot. What if letters that must match exactly could skip straight past whole branches?
HINT 2 THE STRUCTURE
A trie turns 'skip past what can't match' into 'follow one child pointer.' A literal letter picks exactly one child; a dot is the one spot where you have to try more than one.
HINT 3 ONE STEP FROM THE ANSWER
DFS the trie: on a normal letter, follow the single matching child or fail immediately; on a dot, recurse into every child at that depth and succeed the moment any branch completes the word.
Trie holds run, fun, sun — three added words sharing the suffix 'un'. Query '.un': dot, then literal u, then literal n.
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True
def search(self, word: str) -> bool:
def dfs(node: TrieNode, i: int) -> bool:
if i == len(word):
return node.is_word
ch = word[i]
if ch == ".":
return any(dfs(child, i + 1) for child in node.children.values())
child = node.children.get(ch)
return child is not None and dfs(child, i + 1)
return dfs(self.root, 0)class WordDictionary:
def __init__(self):
self.words = []
def addWord(self, word: str) -> None:
self.words.append(word)
def search(self, word: str) -> bool:
for w in self.words:
if len(w) != len(word):
continue
if all(qc == "." or qc == wc for qc, wc in zip(word, w)):
return True
return Falseclass WdTrieNode {
Map<Character, WdTrieNode> children = new HashMap<>();
boolean isWord = false;
}
class WordDictionary {
private final WdTrieNode root = new WdTrieNode();
public WordDictionary() {
}
public void addWord(String word) {
WdTrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new WdTrieNode());
}
node.isWord = true;
}
public boolean search(String word) {
return dfs(root, word, 0);
}
private boolean dfs(WdTrieNode node, String word, int i) {
if (i == word.length()) {
return node.isWord;
}
char c = word.charAt(i);
if (c == '.') {
for (WdTrieNode child : node.children.values()) {
if (dfs(child, word, i + 1)) {
return true;
}
}
return false;
}
WdTrieNode child = node.children.get(c);
return child != null && dfs(child, word, i + 1);
}
}class WordDictionary {
private final List<String> words = new ArrayList<>();
public WordDictionary() {
}
public void addWord(String word) {
words.add(word);
}
public boolean search(String word) {
for (String w : words) {
if (w.length() != word.length()) {
continue;
}
boolean match = true;
for (int i = 0; i < word.length(); i++) {
char qc = word.charAt(i);
if (qc != '.' && qc != w.charAt(i)) {
match = false;
break;
}
}
if (match) {
return true;
}
}
return false;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED