0826MediumArrayStringTrie

Codes Close to a Known Part

Tracked in this browser only

Trains the technique from

LeetCode 2452Words Within Two Edits of Dictionary

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def near_match_codes(queries: list[str], dictionary: list[str]) -> list[int]:

Java

public List<Integer> nearMatchCodes(String[] queries, String[] dictionary)

The intended approach

Time O(q * d * n) for q read codes, d stocked codes and length n, with the inner walk cut short past two differences.Space O(1) beyond the returned list of slots.

Because the two codes always have equal length, the number of letters that would have to be overwritten is just the number of slots where they differ. Walk each read code against each stocked code counting those slots, abandoning the pair as soon as the count passes two, and record the read code's slot on the first stocked code that is close enough.

Pythonentry point: near_match_codes

def near_match_codes(queries, dictionary):
    # every code is the same length, so a mismatch tally is a single walk
    out = []
    for pos, code in enumerate(queries):
        for known in dictionary:
            off = 0
            for a, b in zip(code, known):
                if a != b:
                    off += 1
                    if off > 2:
                        break
            if off <= 2:
                out.append(pos)
                break
    return out

The obvious version

For each read code, build the full list of differing slots against every stocked code and check whether any list is shorter than three. Materialises every difference list rather than counting and cutting short.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_near_match_codes(queries, dictionary):
    out = []
    for pos in range(len(queries)):
        hit = False
        for known in dictionary:
            gaps = [i for i in range(len(known)) if queries[pos][i] != known[i]]
            if len(gaps) < 3:
                hit = True
        if hit:
            out.append(pos)
    return out

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in