954. Searching With a Dot
Run q operations against a growing set of words.
add w store the word w
find p print yes if some stored word MATCHES the pattern p, else no
A pattern matches a word when they have the SAME LENGTH and, at every position,
either the pattern has the same letter as the word or the pattern has a .,
which stands for exactly one letter of any kind.
``` add bad, add dad, add mad find pad -> no find bad -> yes find .ad -> yes
add bad find b.. -> yes find ..d -> yes find ... -> yes
add ab, add abc find ab. -> yes find .. -> yes find .... -> no ```
The last line is the one people get wrong. A dot stands for exactly one letter, never for nothing and never for several, so a pattern of four dots matches no stored word of length two or three.
## Why the plain walk stops working
Problem 940's walk has one child to step into at each character, so it is a
straight line down the trie. A . has 26 possible steps, and which of them leads
to a match is not known until the rest of the pattern has been checked.
Scanning the stored words instead costs, with 10000 words and 10000 patterns, 10^8 word comparisons of up to 12 characters, so 1.2 * 10^9 character comparisons.
## The walk becomes a search
Turn the walk into a recursion that carries a node and a position in the pattern.
search(node, k):
if k == length(p): return isEnd[node]
if p[k] is '.':
for c in a .. z:
if child[node][c] exists and search(child[node][c], k+1): return true
return false
c = p[k]
return child[node][c] exists and search(child[node][c], k+1)
A letter narrows to one child. A dot tries every child that exists, and the words that no longer fit are simply not there to try.
## Why this is far better than 26 to the power of the number of dots
At depth k the search can only ever stand on nodes at depth k of the trie, so
the number of states it can reach is bounded by the number of nodes, not by
26^(dots). A pattern of twelve dots against a trie built from 20000 words of
twelve letters visits at most those 240001 nodes once each, because a node can
be reached only along the one path that spells it.
The trie is doing the pruning: a branch that does not exist is a branch not taken, and the more the stored words share, the fewer branches there are.
## The two boundaries
The length has to match exactly, which the recursion gets right for free by
testing isEnd only when k has reached the end of the pattern. Returning true
at a node with children but no end flag would accept ab. against the stored
word abcd.
Finding nothing is not an error. A pattern of all dots against an empty set
answers no, and the recursion must be able to run with a root that has no
children at all.
## Against problem 955
955 asks HOW MANY stored words a pattern matches rather than whether any does, so it cannot stop at the first hit and has to sum over every branch the dots open. The recursion is the same shape with a different return type.
## Cost
Each add is the length of the word. Each find visits at most one node per
trie node, so O(nodes) in the worst case and far less in practice. Space is the
trie, at most 1 + 20000 * 12 = 240001 nodes.
Constraints - `1 ≤ q ≤ 20000` - Every stored word is 1 to 12 lowercase English letters. - Every pattern is 1 to 12 characters, each a lowercase English letter or a `.`. - At least one operation is a `find`.
Input
The first line contains one integer q.
Each of the next q lines is add w or find p. Here w is lowercase letters
and p is lowercase letters and dots.
Output
For each find operation, in order, print yes if at least one stored word matches the pattern and no if none does, one answer on its own line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.