2452. Words Within Two Edits of Dictionary

Problem statement

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

In one edit, you can change any one character in a query word to any other character.

Return all words from queries that can become equal to at least one word in dictionary using at most two edits.

The order of the returned words should be the same as in queries.

Examples

Example 1

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

Explanation:

• "word" differs from "wood" in only one position
• "note" differs from "joke" in two positions
• "ants" needs more than two edits for every dictionary word
• "wood" already matches "wood"

So the answer is ["word", "note", "wood"].

Example 2

Input: queries = ["yes"], dictionary = ["not"]
Output: []

No dictionary word can be reached within two edits.

Constraints

• 1 <= queries.length, dictionary.length <= 100
• n == queries[i].length == dictionary[j].length
• 1 <= n <= 100
• All strings contain lowercase English letters

Explanation

The constraints are small enough that a brute-force solution is completely fine here.

Why?

• up to 100 query words
• up to 100 dictionary words
• each word length up to 100

So checking every query against every dictionary word gives roughly 100 * 100 * 100 = 10^6 character comparisons, which is easily acceptable.

The idea is simple:

1. take one word from queries
2. compare it with every word in dictionary
3. count how many positions are different
4. if the difference is at most 2, include the query word in the answer and stop checking further dictionary words

That is all we need.

Code

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;

        for (auto& s : queries) {
            for (auto& d : dictionary) {
                int diff = 0;

                for (int i = 0; i < s.length(); i++) {
                    if (s[i] != d[i]) diff++;
                }

                if (diff <= 2) {
                    ans.push_back(s);
                    break;
                }
            }
        }

        return ans;
    }
};