Words Within Two Edits of Dictionary

Med

#2236Time: 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.

Data structures

Array String Trie

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Initialize a HashSet<String> called matchingQueries.
For each query in the queries array:
For each dictWord in the dictionary array:
Compare query and dictWord character by character and count the differences.
If the difference count is _ <= 2, add the query to the matchingQueries set.
After checking all pairs, we construct the final list in the original order.
Initialize an empty List<String> called result.
Iterate through the original queries array one more time.
For each query, if it exists in our matchingQueries set, add it to the result list.
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.

1import java.util.ArrayList;2import java.util.HashSet;3import java.util.List;4import java.util.Set;5 6class Solution {7    public List<String> twoEditWords(String[] queries, String[] dictionary) {8        Set<String> matchingQueries = new HashSet<>();9        for (String query : queries) {10            for (String dictWord : dictionary) {11                int diff = 0;12                for (int i = 0; i < query.length(); i++) {13                    if (query.charAt(i) != dictWord.charAt(i)) {14                        diff++;15                    }16                }17                if (diff <= 2) {18                    matchingQueries.add(query);19                    // This version doesn't break, so it might do extra work.20                }21            }22        }23 24        List<String> result = new ArrayList<>();25        for (String query : queries) {26            if (matchingQueries.contains(query)) {27                result.add(query);28            }29        }30        return result;31    }32}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

Initialize an empty List<String> called result.
For each query in the queries array:
For each dictWord in the dictionary array:
Check if the number of differing characters between query and dictWord is at most 2.
If it is, add the query to the result list.
Then, break from the inner loop to proceed to the next query.
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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> twoEditWords(String[] queries, String[] dictionary) {6        List<String> result = new ArrayList<>();7        for (String query : queries) {8            for (String dictWord : dictionary) {9                if (isMatch(query, dictWord)) {10                    result.add(query);11                    break; // Optimization: Found a match, move to the next query.12                }13            }14        }15        return result;16    }17 18    private boolean isMatch(String s1, String s2) {19        int diff = 0;20        for (int i = 0; i < s1.length(); i++) {21            if (s1.charAt(i) != s2.charAt(i)) {22                diff++;23            }24            // Further optimization: if diff is already > 2, no need to check further.25            if (diff > 2) {26                return false;27            }28        }29        return true; // If loop finishes, diff must be <= 2.30    }31}

Complexity

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

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public IList < string > TwoEditWords(string[] queries, string[] dictionary) {3        var ans = new List < string > ();4        foreach(var s in queries) {5            foreach(var t in dictionary) {6                int cnt = 0;7                for (int i = 0; i < s.Length; i++) {8                    if (s[i] != t[i]) {9                        cnt++;10                    }11                }12                if (cnt < 3) {13                    ans.Add(s);14                    break;15                }16            }17        }18        return ans;19    }20}

1class Solution {2public3  List<String> twoEditWords(String[] queries, String[] dictionary) {4    List<String> ans = new ArrayList<>();5    int n = queries[0].length();6    for (var s : queries) {7      for (var t : dictionary) {8        int cnt = 0;9        for (int i = 0; i < n; ++i) {10          if (s.charAt(i) != t.charAt(i)) {11            ++cnt;12          }13        }14        if (cnt < 3) {15          ans.add(s);16          break;17        }18      }19    }20    return ans;21  }22}

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

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem