380. Words Within Two Edits of Dictionary

All words have the same length, and a single edit changes one position. So an edit distance of at most 2 is the same as a Hamming distance of at most 2. For each query, scan the dictionary and check.

Approach

1. For each query word q:
   • For each dictionary word d:
     • Count mismatching positions; stop early if the count exceeds 2.
     • If the final count is ≤ 2, accept q and move on.

Complexity

• Time: O(q · d · n) where q, d are the array sizes and n is the word length. With all bounded by 100, this is fine (≈10⁶ ops).
• Space: O(q) — output list.

import java.util.*;

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> result = new ArrayList<>();
        for (String q : queries) {
            for (String d : dictionary) {
                int mismatches = 0;
                for (int i = 0; i < q.length(); i++) {
                    if (q.charAt(i) != d.charAt(i)) mismatches++;
                    if (mismatches > 2) break;
                }
                if (mismatches <= 2) {
                    result.add(q);
                    break;
                }
            }
        }
        return result;
    }
}

Since all words have equal length, an edit (change-one-letter) is the same as a position where two strings differ — Hamming distance. So "within two edits" means "differs in at most 2 positions". A query word qualifies if any dictionary word matches it in at least n - 2 positions.

The edit-distance shortcut

The general edit-distance problem allows insertion, deletion, and substitution. But here all words share the same length n, and the only operation listed is "change any letter to another letter" (substitution). Insertions or deletions would change the length, so they're not even possible.

Under that restriction, the minimum number of edits to turn q into d is just the count of mismatching positions:

edits(q, d) = sum(q[i] != d[i] for i in range(n))   ← Hamming distance

So "q is within two edits of some dictionary word" simplifies to "there exists d in dictionary with at most 2 mismatching positions vs. q".

Steps

1. Initialise result = [].
2. For each query q:
   • For each dictionary word d:
     • Compare position by position; count mismatches; break early when the count exceeds 2.
     • If the count is ≤ 2, append q to result and move to the next query (no need to check more dictionary words).
3. Return result.

Walk-through

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

Result: ["word", "note", "wood"].

Edge cases

• Identical query and dictionary entry: 0 mismatches, immediately accepted.
• Single-character words: at most 1 mismatch possible — every query qualifies as long as the dictionary is non-empty.
• Empty dictionary: every query is rejected (the inner loop never finds a match).

A note on scaling

For larger constraints (say n = 10^4, dictionary size 10^4), this O(q · d · n) approach would be slow and a trie with depth-bounded search becomes attractive. For the given limits (n, q, d ≤ 100 → ≈10⁶ ops), the simple version is the cleanest choice.

Complexity

• Time: O(q · d · n) worst case.
• Space: O(q) — the result list.