957. Exactly One Letter Different
A dictionary of n words is given, then q queries. For each query print yes
if some dictionary word has the SAME LENGTH as the query and differs from it in
EXACTLY ONE position, and no otherwise.
The word must actually differ. A query that is itself in the dictionary does not count unless some other dictionary word is also one letter away.
``` dictionary hello leetcode hallo hello -> yes hallo differs from it only at position 1 hhllo -> yes hello differs from it only at position 1 hell -> no no dictionary word has length 4 leetcoded -> no length 9 against a dictionary word of length 8
dictionary a b -> yes a -> no aa -> no ```
## The scan, and why the trie helps
Comparing the query with every dictionary word costs n comparisons of up to 12
characters, so 20000 * 2000 * 12 is about 4.8 * 10^8 character comparisons at
the limits, and every query redoes the shared prefixes from scratch.
A trie shares them. Two dictionary words with the same first eight letters are compared against the query's first eight letters once, not twice.
## A walk with a budget
Carry a mismatch budget down the walk. At each position you may step into the child matching the query's letter for free, or into any other existing child at a cost of one, and the budget is one in total.
search(node, k, used):
if k == length(query): return used == 1 and isEnd[node]
for c in a .. z:
if child[node][c] is absent: continue
cost = 0 if c == query[k] else 1
if used + cost <= 1 and search(child[node][c], k+1, used+cost): return true
return false
## Why the answer is used == 1 and not used <= 1
The question asks for exactly one difference. Accepting used == 0 would say
yes for any query that is itself in the dictionary, which is the single most
common mistake here and is why the fourth example exists.
Accepting a budget of one anywhere on the path is still correct for "exactly
one", because a walk that finishes with used == 1 has differed in exactly one
position by construction: every other step was a free step, and a free step means
equality.
## Why the search cannot explode
The states reachable with used == 0 are exactly the nodes along the query's own
path, which is at most 13 of them. From each of those, spending the budget opens
at most 25 branches, and after that every step is forced, because a budget of
zero leaves only the matching child. So the whole search is at most about
13 * 25 * 12 steps, which is a few thousand per query with no memoisation needed.
## Lengths take care of themselves
Nothing in the code compares lengths. A dictionary word shorter than the query
ends before k reaches the end, so its node has no child to step into. A longer
one is reached with k exhausted but isEnd false. The base case rejects both.
## Against problem 958
958 allows an insertion or a deletion as well, which means the position in the query and the depth in the trie can come apart, so the walk needs a step that advances one without the other. Here they always move together, which is what keeps this one simple.
## Cost
Building is O(total characters). Each query is a few thousand steps at the
limits. Space is the trie, at most 1 + 20000 * 12 = 240001 nodes.
Constraints - `1 ≤ n ≤ 20000` - `1 ≤ q ≤ 2000` - Every dictionary word and every query is 1 to 12 lowercase English letters. - Dictionary words may repeat.
Input
The first line contains an integer n.
The next n lines each contain one dictionary word.
The next line contains an integer q.
The next q lines each contain one query string.
Output
For each query, in order, print yes if some dictionary word has the same length and differs in exactly one position, and no otherwise, one answer per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.