Leetcode: 2452. Words Within Two Edits of Dictionary

Problem Statement

Understand the problem

Given a dictionary and queries, return a subarray of queries which each query \(q\) appear in the dictionary if edit distance (only change) at most 2.

Devise a plan

Pattern: Small constraints could allow a brute-force solution. For each query, compute the edit distance to all words in the dictionary and add it to the output if the distance is at most 2.

Carry out the plan

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        return [
            q
            for q in queries
            if any(sum(a != b for a, b in zip(q, d)) <= 2 for d in dictionary)
        ]