2452. Words Within Two Edits of Dictionary

Intuition

Because all words have the same fixed length, two words are "within two edits" of each other if and only if the count of positions where their characters differ is at most 2. There is no insertion or deletion — only substitution. We can therefore check every (query, dictionary) pair in a single character-by-character scan and short-circuit as soon as the mismatch count exceeds 2.

Algorithm

1For each word `q` in `queries`, iterate over every word `w` in `dictionary`.
2Count the number of positions i where `q[i] != w[i]`. Stop early if the count reaches 3.
3If the final count is less than 3 (i.e., 0, 1, or 2 mismatches), add `q` to the result list and break — no need to check further dictionary words for this query.
4Return the result list.

Example Walkthrough

Input: queries = ["word","note","ants"], dictionary = ["wood","joke","moat"]

1."word" vs "wood": diff at index 2 (r≠o) and index 3 (d≠d — same). 1 mismatch → "word" qualifies.
2."note" vs "wood": diff at 0 (n≠w), 1 (o≠o — same), 2 (t≠o), 3 (e≠d). 3 mismatches — skip.
3."note" vs "joke": diff at 0 (n≠j), 2 (t≠k). 2 mismatches → "note" qualifies.
4."ants" vs "wood": 4 mismatches. vs "joke": 4. vs "moat": diff at 0 (a≠m), 2 (t≠a), 3 (s≠t). 3 mismatches — no match.

Output: ["word", "note"]

Common Pitfalls

•This problem only involves substitution edits (same-length words) — do NOT use a full Levenshtein edit-distance algorithm, which is far slower.
•Break out of the inner loop as soon as any dictionary word matches; avoid redundant comparisons.
•Early exit inside GetDiff when diff reaches 3 is a small but effective constant-factor optimisation.

2452.cs

// Approach: For each word in `queries`, we compare it against every word in `dictionary`.
// Since all words have the same length, we iterate through characters and count the differences.
// If we find a dictionary word where the difference is at most 2 (i.e., less than 3 edits), we add
// the query word to the result list and stop checking further dictionary words for this query.
// This brute-force pairing approach works efficiently within the constraints.
//
// Time: O(Q * D * L), where Q is the number of query words, D is the number of dictionary words, and L is the string length.
// Space: O(1) auxiliary space (excluding the output list), as we only count character differences.

public class Solution
{
    public IList<string> TwoEditWords(string[] queries, string[] dictionary)
    {
        var ans = new List<string>();

        foreach (var query in queries)
        {
            foreach (var word in dictionary)
            {
                if (GetDiff(query, word) < 3)
                {
                    ans.Add(query);
                    break;
                }
            }
        }

        return ans;
    }

    private int GetDiff(string query, string word)
    {
        int diff = 0;
        for (int i = 0; i < query.Length; ++i)
        {
            if (query[i] != word[i])
                ++diff;
        }
        
        return diff;
    }
}

Was this solution helpful?