Wildcard Word Search
Problem
Build a dictionary from a list of words, then answer search queries where a . in the query matches any single character. A query matches only if some stored word has exactly the same length and agrees on every non-dot position.
Examples
Input: words = ["bad", "dad", "mad"], query = ".ad"
Output: True
Why: the dot can stand for b, d or mInput: words = ["bad", "dad", "mad"], query = "pad"
Output: False
Why: no stored word starts with pInput: words = ["bad"], query = "ba"
Output: False
Why: edge case, a prefix is not a stored wordHints
0 / 3
Checking every stored word against every query re-reads the same shared prefixes over and over. The words have structure you can store once.
A trie collapses shared prefixes into shared nodes, so 'bad', 'dad' and 'mad' meet again at their second character.
Walk the trie one query character at a time. A real character follows the single matching child, if it exists. A dot has to try every child, so recurse into each one and succeed if any branch reaches a node marked as a word end.
Solution
A nested-dictionary trie stores each word once along a path, with a sentinel key marking where a word ends. A concrete character narrows the search to one child; a dot forks into all of them, which is the only place backtracking happens. A query with no dots costs O(m) for length m. Each dot multiplies the work by the branching factor, so the worst case is O(26^d · m) for d dots — still far cheaper than scanning every word when dots are few.
def build(words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {}) # shared prefixes share nodes
node["$"] = True # sentinel: a word ends here
return root
def search(node, pattern, i=0):
if i == len(pattern):
return "$" in node # a prefix is not a word
ch = pattern[i]
if ch != ".":
return ch in node and search(node[ch], pattern, i + 1)
return any(search(kid, pattern, i + 1) for k, kid in node.items() if k != "$")
t = build(["bad", "dad", "mad"])
print(search(t, ".ad"), search(t, "pad")) # -> True False
print(search(build(["bad"]), "ba")) # -> FalseStuck on the idea rather than the code? Trie Basics covers it.