Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

All words have equal length, and an edit replaces one character. The minimum edits between a query and a dictionary word are therefore exactly the number of differing positions, with no insertion/deletion dynamic programming needed.

Approach

For each query, compare it with dictionary words character by character and count mismatches. If any dictionary word differs in at most two positions, append the query once and stop checking it. Otherwise omit it. Return accepted queries in their original order. Zero, one, and two mismatches all qualify, and repeated matching queries remain repeated because the output preserves query occurrences.

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        n = len(queries[0])
        res = []

        for query in queries:
            for word in dictionary:
                edits = 0
                for i in range(n):
                    if query[i] != word[i]:
                        edits += 1
                if edits <= 2:
                    res.append(query)
                    break

        return res

Complexity analysis

Let q = queries.length, d = dictionary.length, and L be the common word length. Time: O(q * d * L) in the worst case. Auxiliary space: O(1) excluding the returned list, which uses O(q) space in the worst case.