A community ham-radio registry keeps a list of station call-names. To save airtime during drills, operators refer to a station by a short fingerprint instead of spelling it out: if the call-name has one or two letters, its fingerprint is the call-name itself; otherwise the fingerprint is formed by the call-name's first letter, followed by the number of letters strictly between the first and the last letter, followed by the last letter (so a ten-letter call-name beginning with 'c' and ending with 'd' becomes 'c8d'). Because two different call-names can accidentally reduce to the same fingerprint, an operator wants to know, for a list of lookup call-names, whether each one can be used safely — that is, whether every registry entry sharing its fingerprint is in fact the very same call-name (so no other, different call-name is hiding behind that fingerprint). The registry itself may list the same call-name more than once; repeats of a lookup's own call-name never make it unsafe.
n, the number of entries in the registry.n lines: one registry call-name each, consisting only of lowercase English letters.q, the number of lookup call-names.q lines: one lookup call-name each, consisting only of lowercase English letters.q lines. Line i must be true if the fingerprint of the i-th lookup call-name is safe to use as defined above, or false otherwise.n <= 1000q <= 1000Example 1
Input
4 deer door cake card 2 dear cart
Expected
false true
Explanation
deer and door both have the fingerprint d2r; the lookup dear also reduces to d2r, and since two different call-names (deer and door) share that fingerprint, dear is unsafe: false. cart reduces to c2t, which nothing else in the registry maps to (card maps to c2d), so cart is safe: true.
Example 2
Input
3 cake cane bb 2 cane bb
Expected
false true
Explanation
cane and cake both reduce to the fingerprint c2e; since cake is a different call-name sharing that fingerprint, the lookup cane is unsafe even though cane itself is in the registry: false. bb has only two letters, so its own fingerprint is the literal string 'bb', which no other registry entry matches: true.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →