# Words Within Two Edits of Dictionary
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/words-within-two-edits-of-dictionary)
Canonical: https://scaleengineer.com/dsa/problems/words-within-two-edits-of-dictionary
**Data structures:** Array, String, Trie
---
## 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 from_ `queries`_,_ _that match with some word from_ `dictionary` _after a maximum of **two edits**_. Return the words in the **same order** they appear in `queries`.

**Example 1:**

**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:**

**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.

# Approaches
## Brute-Force Comparison
This approach uses a straightforward, nested loop structure to solve the problem. We iterate through each word in the `queries` array. For each query word, we then iterate through every single word in the `dictionary` array. In the innermost loop, we compare the query word and the dictionary word character by character to count the number of differences. If this count is two or less, we've found a potential match. To ensure we return the results in the original order and without duplicates, we use a `HashSet` to store all valid queries and then filter the original `queries` list based on the content of the set.
**Time:** O(Q * D * L), where `Q` is the number of queries, `D` is the number of dictionary words, and `L` is the length of the words. The nested loops dominate the runtime. There is an additional `O(Q * L)` cost for the final pass, but it's absorbed by the main term. · **Space:** O(Q * L), where `Q` is the number of queries and `L` is the length of each word. This is for the `HashSet` which, in the worst case, could store all the query words.
**Pros:** The logic is simple and easy to understand.; It correctly solves the problem by ensuring all possible pairs are checked.
**Cons:** It performs unnecessary comparisons by not stopping after finding the first match for a query.; It requires extra space for the `HashSet` to store matching queries.; It needs a final pass over the `queries` array to reconstruct the output in the correct order, adding a bit of overhead.
### Explanation
The core idea is to exhaustively check every query against every dictionary word. To manage the results, we first identify all query words that have at least one valid match and store them in a temporary data structure, like a `HashSet`, which automatically handles duplicates.

Here's the breakdown of the algorithm:
1.  Initialize a `HashSet<String>` called `matchingQueries`.
2.  For each `query` in the `queries` array:
3.  For each `dictWord` in the `dictionary` array:
4.  Compare `query` and `dictWord` character by character and count the differences.
5.  If the difference count is `_ <= 2`, add the `query` to the `matchingQueries` set.
6.  After checking all pairs, we construct the final list in the original order.
7.  Initialize an empty `List<String>` called `result`.
8.  Iterate through the original `queries` array one more time.
9.  For each `query`, if it exists in our `matchingQueries` set, add it to the `result` list.
10. Return the `result` list.

This method is correct but slightly inefficient because it continues to check a query against the rest of the dictionary even after a match has been found, and it requires extra space and an extra pass to restore the order.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        Set<String> matchingQueries = new HashSet<>();
        for (String query : queries) {
            for (String dictWord : dictionary) {
                int diff = 0;
                for (int i = 0; i < query.length(); i++) {
                    if (query.charAt(i) != dictWord.charAt(i)) {
                        diff++;
                    }
                }
                if (diff <= 2) {
                    matchingQueries.add(query);
                    // This version doesn't break, so it might do extra work.
                }
            }
        }

        List<String> result = new ArrayList<>();
        for (String query : queries) {
            if (matchingQueries.contains(query)) {
                result.add(query);
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize a `HashSet<String>` to store the queries that have a match in the dictionary.
- Iterate through each `query` string in the `queries` array.
- For each `query`, iterate through each `dictWord` string in the `dictionary` array.
- Inside the inner loop, compare the `query` and `dictWord` character by character to count the number of differing characters (the Hamming distance).
- If the difference count is less than or equal to 2, add the current `query` string to the `HashSet`. Note that this version continues checking the query against other dictionary words even after a match is found.
- After the loops complete, initialize a new empty `List<String>` to store the final result.
- Iterate through the original `queries` array again. For each `query`, check if it is present in the `HashSet`.
- If it is, add it to the final result list. This step is necessary to return the words in their original order.
- Return the final result list.

## Optimized Brute-Force with Early Exit
This approach improves upon the naive brute-force method by adding a simple but effective optimization. The core logic remains the same: we iterate through each query and compare it against dictionary words. However, as soon as we find a dictionary word that is within two edits of the current query word, we know this query is valid. There is no need to check it against the rest of the dictionary. We can immediately add the query to our result list and move on to the next one.
**Time:** O(Q * D * L) in the worst case. `Q` is the number of queries, `D` is the number of dictionary words, and `L` is the word length. However, the average-case performance is much better because of the early exit from the inner loop. · **Space:** O(1), excluding the space required for the output list. This is an improvement over the previous approach that required a `HashSet`.
**Pros:** More efficient on average than the naive brute-force approach due to the early exit.; Requires no extra space (besides the output list), making it more memory-efficient.; Preserves the original order of queries naturally, simplifying the logic.
**Cons:** The worst-case time complexity remains `O(Q * D * L)`, which occurs if no matches are found or if matches are always the last words in the dictionary.
### Explanation
By adding an early exit, we can significantly improve the average-case performance and reduce space usage. The moment a match is found for a given query, we add it to our results and break from the inner loop that iterates over the dictionary. This avoids many unnecessary comparisons.

The algorithm is as follows:
1.  Initialize an empty `List<String>` called `result`.
2.  For each `query` in the `queries` array:
3.  For each `dictWord` in the `dictionary` array:
4.  Check if the number of differing characters between `query` and `dictWord` is at most 2.
5.  If it is, add the `query` to the `result` list.
6.  Then, `break` from the inner loop to proceed to the next query.
7.  Return the `result` list.

This approach is more efficient in terms of both time (on average) and space. It naturally preserves the order of the queries because we add them to the result list as we encounter them in the original `queries` array, so no extra data structures or passes are needed.

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

class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> result = new ArrayList<>();
        for (String query : queries) {
            for (String dictWord : dictionary) {
                if (isMatch(query, dictWord)) {
                    result.add(query);
                    break; // Optimization: Found a match, move to the next query.
                }
            }
        }
        return result;
    }

    private boolean isMatch(String s1, String s2) {
        int diff = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
            // Further optimization: if diff is already > 2, no need to check further.
            if (diff > 2) {
                return false;
            }
        }
        return true; // If loop finishes, diff must be <= 2.
    }
}
```
### Algorithm
- Initialize an empty `List<String>` to store the result.
- Iterate through each `query` string in the `queries` array.
- For each `query`, start an inner loop to iterate through each `dictWord` in the `dictionary` array.
- Create a helper function, `isMatch(query, dictWord)`, that compares the two strings.
- Inside the helper function, count the character differences. For a small optimization, if the difference count ever exceeds 2, the function can immediately return `false`.
- If the helper function returns `true` (meaning the difference is 0, 1, or 2), add the current `query` to the result list.
- Crucially, after adding the query, `break` the inner loop to stop checking this query against the rest of the dictionary words.
- Proceed to the next `query` in the outer loop.
- After iterating through all queries, return the result list.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < string > TwoEditWords(string[] queries, string[] dictionary) {
        var ans = new List < string > ();
        foreach(var s in queries) {
            foreach(var t in dictionary) {
                int cnt = 0;
                for (int i = 0; i < s.Length; i++) {
                    if (s[i] != t[i]) {
                        cnt++;
                    }
                }
                if (cnt < 3) {
                    ans.Add(s);
                    break;
                }
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  List<String> twoEditWords(String[] queries, String[] dictionary) {
    List<String> ans = new ArrayList<>();
    int n = queries[0].length();
    for (var s : queries) {
      for (var t : dictionary) {
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
          if (s.charAt(i) != t.charAt(i)) {
            ++cnt;
          }
        }
        if (cnt < 3) {
          ans.add(s);
          break;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> twoEditWords(vector<string> &queries,
                              vector<string> &dictionary) {
    vector<string> ans;
    for (auto &s : queries) {
      for (auto &t : dictionary) {
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i)
          cnt += s[i] != t[i];
        if (cnt < 3) {
          ans.emplace_back(s);
          break;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]: ans = [] for s in queries: for t in dictionary: if sum(a != b for a, b in zip(s, t)) < 3: ans . append(s) break return ans

```