Words Within Two Edits of Dictionary
Problem
You are given two string arrays queries and dictionary. Every word in both arrays has the same length n. One edit changes a single letter of a query word to any other letter. Return every query word that can be turned into some dictionary word using at most two edits, in their original order.
Because both words have equal length, the minimum number of edits between a query and a dictionary word is just the count of positions where their letters differ (the Hamming distance). A query qualifies if that count is ≤ 2 for at least one dictionary word.
queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]["word","note","wood"]def twoEditWords(queries, dictionary):
result = []
for q in queries: # each query word, keep order
for d in dictionary: # try every dictionary word
diff = 0
for i in range(len(q)): # count mismatched positions
if q[i] != d[i]:
diff += 1
if diff > 2: # early exit, can't qualify
break
if diff <= 2: # within two edits
result.append(q)
break # one match is enough
return resultfunction twoEditWords(queries, dictionary) {
const result = [];
for (const q of queries) { // each query word, keep order
for (const d of dictionary) { // try every dictionary word
let diff = 0;
for (let i = 0; i < q.length; i++) { // count mismatched positions
if (q[i] !== d[i]) {
diff++;
if (diff > 2) break; // early exit, can't qualify
}
}
if (diff <= 2) { // within two edits
result.push(q);
break; // one match is enough
}
}
}
return result;
}List<String> twoEditWords(String[] queries, String[] dictionary) {
List<String> result = new ArrayList<>();
for (String q : queries) { // each query word, keep order
for (String d : dictionary) { // try every dictionary word
int diff = 0;
for (int i = 0; i < q.length(); i++) { // count mismatches
if (q.charAt(i) != d.charAt(i)) {
diff++;
if (diff > 2) break; // early exit
}
}
if (diff <= 2) { // within two edits
result.add(q);
break; // one match is enough
}
}
}
return result;
}vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
vector<string> result;
for (auto& q : queries) { // each query word, keep order
for (auto& d : dictionary) { // try every dictionary word
int diff = 0;
for (int i = 0; i < (int)q.size(); i++) { // count mismatches
if (q[i] != d[i]) {
diff++;
if (diff > 2) break; // early exit
}
}
if (diff <= 2) { // within two edits
result.push_back(q);
break; // one match is enough
}
}
}
return result;
}Explanation
The key insight is that "edits" here are restricted to substitutions only — you may change a letter, but never insert or delete one. Combined with the guarantee that every query and dictionary word share the same length, this means the minimum number of edits between two words is exactly the number of positions where their characters differ. That count is the Hamming distance.
So a query word qualifies if and only if there exists some dictionary word whose Hamming distance from it is ≤ 2. We never have to think about alignment or insertion costs the way general edit distance (Levenshtein) would require.
The straightforward solution compares every query against every dictionary word. For each pair we scan the characters in lockstep and count mismatches. The moment the running count of differences exceeds 2, we stop early — that pair can no longer help, so there is no point finishing the scan.
As soon as a query finds one dictionary word within two edits, we record the query and break out of the dictionary loop. Appending in the order we iterate queries automatically preserves the required output order.
Although the problem lives under the Trie topic, the constraints are small (at most 100 words on each side, length up to 100), so this clean brute force comfortably fits in time. A trie would help only if we needed to prune shared prefixes across many dictionary words.
Example: for "note" versus "joke", positions 0 (n≠j) and 1 (o vs o match) … actually the mismatches are at index 0 (n≠j) and index 2 (t≠k), giving 2 differences — exactly two edits, so "note" is included.