Show problems as
Classic problem #2452MediumArrayStringTrie

Words Within Two Edits of Dictionary

Real-world version: Codes Close to a Known Part
Tracked in this browser only
Read Words Within Two Edits of Dictionary on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A stockroom scanner reads part codes. Every code in use, and every code the scanner reads, is exactly n lowercase letters long.

queries holds the codes the scanner read, in the order it read them, and dictionary holds the codes the stockroom actually stocks. A read code is recoverable when some stocked code can be reached from it by overwriting at most two of its letters. Overwriting a letter replaces the letter in that slot with any other letter; slots are never inserted or removed, since the length is fixed.

Return the slots of queries holding a recoverable code, in increasing order. A slot is listed once however many stocked codes it is close to.

Examples

Example 1

Input
queries = ["wxyz", "wxpq", "mnop"], dictionary = ["wxab", "mnrs"]
Output
[0, 1, 2]

The code at slot 0 differs from "wxab" in its last two letters. The code at slot 1 also differs from "wxab" in its last two letters. The code at slot 2 differs from "mnrs" in its last two letters.

Example 2

Input
queries = ["cba"], dictionary = ["abc"]
Output
[0]

Slot 0 and the stocked code differ in the first and third letters, which is two slots, so the read code is recoverable.

Example 3

Input
queries = ["zpqr", "pqrs"], dictionary = ["zzzz"]
Output
[]

Both read codes differ from "zzzz" in three or more slots, so neither is recoverable and the answer is empty.

Constraints

  • 1 <= queries.length <= 100
  • 1 <= dictionary.length <= 100
  • 1 <= queries[i].length <= 100
  • queries[i].length == dictionary[0].length
  • Every code in queries and in dictionary has the same length
  • queries[i] and dictionary[j] consist of lowercase English letters only

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def near_match_codes(queries: list[str], dictionary: list[str]) -> list[int]:
Java
public List<Integer> nearMatchCodes(String[] queries, String[] dictionary)

More on the same topics