Words Within Two Edits of Dictionary - Solution & Explanation
Problem Statement
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 <= 100- All
queries[i]anddictionary[j]are composed of lowercase English letters.
Approach Overview
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 1: Edit Distance with Constraint
This approach involves comparing each word in queries against words in dictionary by calculating how many edits are needed to transform one into another. Since we're interested in words that can be made equivalent through at most two edits, the goal is to find query words where the difference is at most two.
The difference between two words can be determined by counting how many corresponding characters differ between them (ignoring the characters that are already the same).
The function two_edits_allowed iterates over each query word and checks if it can be transformed into any word in the dictionary using the helper function can_convert. If the count of differing positions in the two words is two or less, it is considered as a valid match.
Complexity
Time Complexity: O(n * m * l), where n is the length of queries, m is the length of dictionary, and l is the length of each word.
Space Complexity: O(1), as we only store the results in a list which doesn't depend on the number of dictionary words.
Approach 2: Preprocessing the Dictionary
This alternative method involves preprocessing the dictionary by storing words along with their respective possible results after up to two edits. The primary aim is to speed up the search by avoiding redundant computations for each query word.
In this approach, for every dictionary word, generate all possible words that can be formed with at most two edits and store them. When processing queries, simply check if they already exist in this precomputed set.
In this implementation, the function preprocess_dictionary generates all possible words from the dictionary that can be formed by changing up to 2 characters at any position for each dictionary word. The transformed possibilities are inserted into a set for quick lookup during query processing.
Complexity
Time Complexity: O(26^2 * m * l^2), where m is the length of the dictionary list, due to generating possibilities for each letter pair change.
Space Complexity: O(26^2 * m), due to storing all possible combinations in a set.
Approach 3: Brute Force Enumeration
We directly traverse each word s in the array queries, and then traverse each word t in the array dictionary. If there exists a word t whose edit distance from s is less than 3, we add s to the answer array and then exit the inner loop. If there is no such word t, we continue to traverse the next word s.
The time complexity is O(m times n times l), where m and n are the lengths of the arrays queries and dictionary respectively, and l is the length of the word.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Edit Distance with Constraint | Time Complexity: O(n * m * l), where n is the length of |
| Preprocessing the Dictionary | Time Complexity: O(26^2 * m * l^2), where m is the length of the dictionary list, due to generating possibilities for each letter pair change. |
| Brute Force Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Words Within Two Edits of Dictionary | Simple Approach | Overkill Approach | Leetcode 2452 | MIK • codestorywithMIK • 5,028 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Words Within Two Edits of Dictionary easy or hard?
Words Within Two Edits of Dictionary Python/Java solution
How to solve Words Within Two Edits of Dictionary in O(n)?
What is the best approach for Words Within Two Edits of Dictionary?
Is Words Within Two Edits of Dictionary asked at Google/Amazon/Meta?
What data structure is used in Words Within Two Edits of Dictionary?
What is the time complexity of Words Within Two Edits of Dictionary?
Ready to solve this problem?
Practice Words Within Two Edits of Dictionary with our built-in code editor and test cases.
Practice on FleetCode