All problems

Typo-Tolerant Lookup

Medium · trie

A search box forgives exactly one typing slip. You are given a list of known words, dictionary, and a list of queries.

A query is close to a word if the two have the same length and differ in exactly one position, with every other position holding the same letter. Return a list with one entry per query, in the same order: true if the query is close to at least one word in the dictionary, otherwise false.

A query that is itself in the dictionary is not close to that word, because nothing differs. It still counts as close if some other dictionary word is one slip away from it.

Examples

Example 1

Input: dictionary = ["hello", "world", "cat"], queries = ["hallo", "hello", "cot", "cats"]

Output: [true, false, true, false]

"hallo" differs from "hello" in one place and "cot" differs from "cat" in one place. "hello" is in the dictionary but nothing else is one slip away from it. "cats" has no dictionary word of length 4.

Example 2

Input: dictionary = ["abc", "abd"], queries = ["abc", "abe", "xyz"]

Output: [true, true, false]

"abc" is one slip away from "abd". "abe" is one slip away from both words. "xyz" differs from each word in at least two places.

Example 3

Input: dictionary = ["a"], queries = ["a", "b"]

Output: [false, true]

"a" matches itself exactly, which is no slip, and nothing else is in the dictionary. "b" differs from "a" in its only position.

Constraints