Problem

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words fromqueries _,_that match with some word fromdictionary after a maximum oftwo edits. Return the words in the same order they appear in queries.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2

1
2
3
4

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints

  • 1 <= queries.length, dictionary.length <= 100
  • n == queries[i].length == dictionary[j].length
  • 1 <= n <= 100
  • All queries[i] and dictionary[j] are composed of lowercase English letters.

Solution

Method 1 – Brute Force Edit Distance (Hamming Distance)

Intuition

Since all words are the same length and edits are letter substitutions, we can simply count the number of differing positions (Hamming distance) between each query and each dictionary word. If any dictionary word is within 2 edits, we include the query in the answer.

Approach

  1. For each word in queries:
    • For each word in dictionary:
      • Count the number of positions where the letters differ.
      • If the count is ≤ 2, add the query word to the result and break.
  2. Return the result list in the order of queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        for (const string& q : queries) {
            for (const string& d : dictionary) {
                int diff = 0;
                for (int i = 0; i < q.size(); ++i) {
                    if (q[i] != d[i]) ++diff;
                }
                if (diff <= 2) {
                    ans.push_back(q);
                    break;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func twoEditWords(queries []string, dictionary []string) []string {
    ans := []string{}
    for _, q := range queries {
        for _, d := range dictionary {
            diff := 0
            for i := 0; i < len(q); i++ {
                if q[i] != d[i] {
                    diff++
                }
            }
            if diff <= 2 {
                ans = append(ans, q)
                break
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> ans = new ArrayList<>();
        for (String q : queries) {
            for (String d : dictionary) {
                int diff = 0;
                for (int i = 0; i < q.length(); i++) {
                    if (q.charAt(i) != d.charAt(i)) diff++;
                }
                if (diff <= 2) {
                    ans.add(q);
                    break;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun twoEditWords(queries: Array<String>, dictionary: Array<String>): List<String> {
        val ans = mutableListOf<String>()
        for (q in queries) {
            for (d in dictionary) {
                var diff = 0
                for (i in q.indices) {
                    if (q[i] != d[i]) diff++
                }
                if (diff <= 2) {
                    ans.add(q)
                    break
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans: List[str] = []
        for q in queries:
            for d in dictionary:
                diff = sum(a != b for a, b in zip(q, d))
                if diff <= 2:
                    ans.append(q)
                    break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn two_edit_words(queries: Vec<String>, dictionary: Vec<String>) -> Vec<String> {
        let mut ans = Vec::new();
        for q in &queries {
            for d in &dictionary {
                let diff = q.chars().zip(d.chars()).filter(|(a, b)| a != b).count();
                if diff <= 2 {
                    ans.push(q.clone());
                    break;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    twoEditWords(queries: string[], dictionary: string[]): string[] {
        const ans: string[] = [];
        for (const q of queries) {
            for (const d of dictionary) {
                let diff = 0;
                for (let i = 0; i < q.length; i++) {
                    if (q[i] !== d[i]) diff++;
                }
                if (diff <= 2) {
                    ans.push(q);
                    break;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n * k) — For m queries, n dictionary words, and k word length, we compare each pair.
  • 🧺 Space complexity: O(m) — For the result list.