Words Within Two Edits of Dictionary

Problem

We are given two arrays:

• queries
• dictionary

Every word has the same length. In one edit, we can change any one character of a query word.

For each word in queries, we need to check whether it can become any word in dictionary using at most two character changes.

Return the matching query words in their original order.

Key Insight

Because all words have the same length, this is not the classic insert-delete-replace edit distance problem.

Here, one edit means only this:

• choose one index
• replace that character with another lowercase letter

So the number of edits needed to convert one word into another is simply the number of positions where they differ.

That is the Hamming distance.

Approach

For every query, compare it with every dictionary word.

While comparing two words:

1. Count how many positions have different characters.
2. If the count is at most 2, this query is valid.
3. Add the query to the answer and stop checking more dictionary words for it.

The break is important because each query should appear only once in the answer.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> answer = new ArrayList<>();

        for (String query : queries) {
            for (String word : dictionary) {
                int diff = 0;

                for (int i = 0; i < query.length(); i++) {
                    if (query.charAt(i) != word.charAt(i)) {
                        diff++;
                    }
                }

                if (diff <= 2) {
                    answer.add(query);
                    break;
                }
            }
        }

        return answer;
    }
}

Dry Run

Take:

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

For "word":

• compare with "wood"
• positions differ at only r vs o
• difference count is 1
• add "word"

For "note":

• compare with "joke"
• n vs j differs
• t vs k differs
• difference count is 2
• add "note"

For "ants":

• every dictionary word needs more than two changes
• skip it

For "wood":

• compare with "wood"
• difference count is 0
• add "wood"

Answer:

["word", "note", "wood"]

Why Brute Force Is Enough

The constraints are small:

• queries.length <= 100
• dictionary.length <= 100
• word length <= 100

So checking every query against every dictionary word is only about:

100 * 100 * 100 = 1,000,000

That is completely fine.

Trie Alternative

A trie can also solve this problem by inserting dictionary words and DFS-searching each query while tracking how many changes have been used.

That works, but for these constraints it adds more code without improving the practical interview solution much.

The cleanest approach is to count mismatched positions directly.

Common Mistakes

1. Using full edit distance

We do not need insertion or deletion.

All words have equal length, and only replacement is allowed.

2. Forgetting to break after a match

If one dictionary word already matches within two edits, the query is valid.

Checking the rest of the dictionary is unnecessary.

3. Reordering the answer

The answer must preserve the original order of queries.

Since we scan queries from left to right and append valid words immediately, the order is naturally preserved.

Complexity

Let:

• q be the number of query words
• d be the number of dictionary words
• n be the length of each word

Time Complexity: O(q * d * n)

For each query, we may compare it with every dictionary word, and each comparison takes O(n).

Space Complexity: O(1) extra

Ignoring the output list, we only use a few variables.