941. Only Exact Lookups
A dictionary of n words is given, then q query words. For each query print
yes if that exact word is in the dictionary and no otherwise.
Nothing here asks about prefixes.
dictionary apple banana cherry, queries apple app grape -> yes, no, no
dictionary ab abc, queries ab abc abcd -> yes, yes, no
dictionary zzzz, queries z zz zzzz -> no, no, yes
## This problem is here to be refused
Having just built a trie, the reflex is to build another one. It works: walk the
query, and answer yes only if you land on a node with the end flag set. But it
is the wrong tool, and knowing why is worth more than another trie.
A trie earns its keep on questions a set cannot answer at all, and there is exactly one such question: what is true of every word sharing a prefix. This problem never asks it. Every query is a whole word compared against whole words, which is precisely what a hash set is for.
## What it costs to use the wrong one
Take the limits: 20000 words of at most 20 letters.
raw text 20000 * 20 = 400000 bytes
trie nodes, worst case 1 + 20000 * 20 = 400001 nodes
a node as a 26-slot array 26 * 8 bytes = 208 bytes
trie, array layout 400001 * 208 = 83200208 bytes
That is about 83 MB of index for 400 KB of words, roughly two hundred times the data, and the lookup is still one walk of up to 20 steps. A hash set stores the 400000 bytes of keys plus its table, and answers in one hash and one comparison.
Both are fast enough here. Only one of them is honest about what it is doing.
## When the trie would win after all
Change one word of the question and the answer flips. If a query could be a PREFIX rather than a whole word, the set has to examine every key it holds, and the trie answers by arriving at a node. Problem 940 is exactly that question, and problem 936 is the counting version of it.
## The boundary worth testing either way
A word that is a prefix of another stored word is still a stored word.
Dictionary ab abc answers yes for both ab and abc, and no for abcd.
An implementation that confuses "is a prefix of something stored" with "is
stored" gets the third one wrong.
## Cost
Building the set is O(total characters). Each query is one hash of at most 20
characters plus one comparison. No arithmetic here can overflow anything: the
largest number in the problem is 20000.
Constraints - `1 ≤ n ≤ 20000` - `1 ≤ q ≤ 20000` - Every dictionary word and every query is 1 to 20 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 word.
Output
For each query, in order, print yes if that exact word appears in the dictionary and no otherwise, 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.