Watch 10 video solutions for Words Within Two Edits of Dictionary, a medium level problem involving Array, String. This walkthrough by Bro Coders has 601 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100n == queries[i].length == dictionary[j].length1 <= n <= 100queries[i] and dictionary[j] are composed of lowercase English letters.Problem Overview: You receive two arrays of equal-length strings: queries and dictionary. For each query, determine whether there exists a dictionary word that differs by at most two characters. If the number of mismatched positions (Hamming distance) is ≤ 2, the query belongs in the result.
Approach 1: Edit Distance with Constraint (Brute Force Check) (Time: O(Q * D * K), Space: O(1))
The straightforward approach compares every query word with every dictionary word. Since all strings have equal length, you simply iterate character-by-character and count mismatches. The key optimization is early termination: once the mismatch count exceeds two, stop checking that pair and move to the next dictionary word. If any dictionary word has ≤ 2 mismatches, the query qualifies for the result. This approach relies purely on iteration and character comparison over arrays and strings. Despite being brute force, it performs well in practice because the mismatch check stops quickly when strings diverge early.
Approach 2: Preprocessing the Dictionary (Pattern Hashing) (Time: O(D * K^2 + Q * K^2), Space: O(D * K^2))
Instead of comparing every query against every dictionary word, preprocess the dictionary into a lookup structure. For each dictionary word, generate patterns where up to two positions are replaced with a wildcard (for example, a*c*). Store these patterns in a hash set. During the query phase, generate the same wildcard patterns for the query and check if any exist in the dictionary set. A match means there exists a dictionary word that differs in at most two positions. This converts repeated pairwise comparisons into constant-time hash lookups. The tradeoff is higher preprocessing cost and additional memory for the pattern index.
Recommended for interviews: Start with the constrained edit-distance scan. Interviewers expect you to notice that strings share the same length and only substitutions matter, so counting mismatched positions solves the problem directly. The brute-force comparison with early stopping is simple, correct, and often acceptable for the given constraints. The preprocessing approach demonstrates deeper optimization skills and familiarity with hashing patterns, which can impress in follow-up discussions about scaling or repeated queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Edit Distance with Constraint | O(Q * D * K) | O(1) | General case with moderate input sizes; simplest implementation for interviews |
| Preprocessing the Dictionary (Pattern Hashing) | O(D * K^2 + Q * K^2) | O(D * K^2) | When dictionary is large or reused across many queries |