Words Within Two Edits of Dictionary solution and explanation
Google
9 more videos on this problem
Words Within Two Edits of Dictionary | Simple Approach | Overkill Approach | Leetcode 2452 | MIKcodestorywithMIK · 14:38 · 5K views
2452. Words Within Two Edits of Dictionary | Leetcode BiWeekly 90 | LeetCode 2452Bro Coders · 6:27 · 721 views
2452. Words Within Two Edits of Dictionary | Leetcode Daily - PythonLeetcode Daily · 6:02 · 263 views
leetcode 2452 |Words Within Two Edits of Dictionary | leetcode POTD| Trie|DFS| DSACode With Vick · 22:15 · 222 views
2452. Words Within Two Edits of Dictionary (Leetcode Medium)Programming Live with Larry · 5:03 · 209 views
Words Within Two Edits of Dictionary | Leetcode 2452 | Java | HindiKernel Queen 👑 · 5:33 · 204 views
Words Within Two Edits of Dictionary | LeetCode 2452 - Pythonimpoldev · 8:16 · 153 views
LeetCode - 2452. Words Within Two Edits of Dictionary | Trie | JavaOrkhan Gasanov · 26:43 · 117 views
Words Within Two Edits of Dictionary | LeetCode 2452Streak To Scale · 5:06 · 108 views
Words Within Two Edits of Dictionary | LeetCode 2452 | Java Code | Developer CoderDeveloper Coder · 9:07 · 82 views
The 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 <= 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).
def two_edits_allowed(queries, dictionary):
def can_convert(q, d):
diff_count = sum(1 for x, y in zip(q, d) if x != y)
return diff_count <= 2
result = []
for q in queries:
if any(can_convert(q, d) for d in dictionary):
result.append(q)
return result
# Example usage:
queries = ["word","note","ants","wood"]
dictionary = ["wood","joke","moat"]
print(two_edits_allowed(queries, dictionary))import java.util.ArrayList;
import java.util.List;
public class TwoEditsAllowed {
public static List<String> twoEditsAllowed(String[] queries, String[] dictionary) {
List<String> result = new ArrayList<>();
for (String q : queries) {
for (String d : dictionary) {
if (canConvert(q, d)) {
result.add(q);
break;
}
}
}
return result;
}
private static boolean canConvert(String q, String d) {
int diffCount = 0;
for (int i = 0; i < q.length(); i++) {
if (q.charAt(i) != d.charAt(i)) {
if (++diffCount > 2) return false;
}
}
return true;
}
public static void main(String[] args) {
String[] queries = {"word", "note", "ants", "wood"};
String[] dictionary = {"wood", "joke", "moat"};
System.out.println(twoEditsAllowed(queries, dictionary));
}
}#include <vector>
#include <string>
#include <algorithm>
bool canConvert(const std::string& q, const std::string& d) {
int diff_count = 0;
for (size_t i = 0; i < q.size(); ++i) {
if (q[i] != d[i]) {
if (++diff_count > 2) return false;
}
}
return true;
}
std::vector<std::string> twoEditsAllowed(std::vector<std::string>& queries, std::vector<std::string>& dictionary) {
std::vector<std::string> result;
for (const auto& q : queries) {
if (std::any_of(dictionary.begin(), dictionary.end(), [&](const std::string& d) { return canConvert(q, d); })) {
result.push_back(q);
}
}
return result;
}
// Example usage
// int main() { // ... }function twoEditsAllowed(queries, dictionary) {
function canConvert(q, d) {
let diffCount = 0;
for (let i = 0; i < q.length; i++) {
if (q[i] !== d[i]) {
if (++diffCount > 2) return false;
}
}
return true;
}
const result = [];
for (const q of queries) {
if (dictionary.some(d => canConvert(q, d))) {
result.push(q);
}
}
return result;
}
// Example usage
const queries = ["word","note","ants","wood"];
const dictionary = ["wood","joke","moat"];
console.log(twoEditsAllowed(queries, dictionary));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool canConvert(const char* q, const char* d) {
int diff_count = 0;
for (int i = 0; i < strlen(q); ++i) {
if (q[i] != d[i]) {
if (++diff_count > 2) return false;
}
}
return true;
}
void twoEditsAllowed(char queries[][100], int q_size, char dictionary[][100], int d_size, char result[][100], int* res_size) {
*res_size = 0;
for (int qi = 0; qi < q_size; ++qi) {
for (int di = 0; di < d_size; ++di) {
if (canConvert(queries[qi], dictionary[di])) {
strcpy(result[*res_size], queries[qi]);
(*res_size)++;
break;
}
}
}
}
// Example usage:
int main() {
char queries[4][100] = {"word", "note", "ants", "wood"};
char dictionary[3][100] = {"wood", "joke", "moat"};
char result[4][100];
int res_size;
twoEditsAllowed(queries, 4, dictionary, 3, result, &res_size);
for (int i = 0; i < res_size; ++i) {
printf("%s\n", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string[] queries = { "word", "note", "ants", "wood" };
string[] dictionary = { "wood", "joke", "moat" };
var result = TwoEditsAllowed(queries, dictionary);
Console.WriteLine(string.Join(", ", result));
}
static List<string> TwoEditsAllowed(string[] queries, string[] dictionary)
{
var result = new List<string>();
foreach (var q in queries)
{
foreach (var d in dictionary)
{
if (CanConvert(q, d))
{
result.Add(q);
break;
}
}
}
return result;
}
static bool CanConvert(string q, string d)
{
int diffCount = 0;
for (int i = 0; i < q.Length; i++)
{
if (q[i] != d[i])
{
if (++diffCount > 2) return false;
}
}
return true;
}
}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.
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.
def preprocess_dictionary(dictionary):
edited_words = set()
for d in dictionary:
n = len(d)
for i in range(n):
for j in range(i + 1, n):
for ch1 in 'abcdefghijklmnopqrstuvwxyz':
for ch2 in 'abcdefghijklmnopqrstuvwxyz':
new_word = list(d)
new_word[i] = ch1
new_word[j] = ch2
edited_words.add(''.join(new_word))
return edited_words
def two_edits_dictionary(queries, dictionary):
edited_words = preprocess_dictionary(dictionary)
return [q for q in queries if q in edited_words]
# Example usage:
queries = ["word","note","ants","wood"]
dictionary = ["wood","joke","moat"]
print(two_edits_dictionary(queries, dictionary))import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.ArrayList;
public class TwoEditsDictionary {
public static Set<String> preprocessDictionary(String[] dictionary) {
Set<String> editedWords = new HashSet<>();
for (String d : dictionary) {
int n = d.length();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (char ch1 = 'a'; ch1 <= 'z'; ch1++) {
for (char ch2 = 'a'; ch2 <= 'z'; ch2++) {
char[] newWord = d.toCharArray();
newWord[i] = ch1;
newWord[j] = ch2;
editedWords.add(new String(newWord));
}
}
}
}
}
return editedWords;
}
public static List<String> twoEditsDictionary(String[] queries, String[] dictionary) {
Set<String> preprocessed = preprocessDictionary(dictionary);
List<String> result = new ArrayList<>();
for (String q : queries) {
if (preprocessed.contains(q)) {
result.add(q);
}
}
return result;
}
public static void main(String[] args) {
String[] queries = { "word", "note", "ants", "wood" };
String[] dictionary = { "wood", "joke", "moat" };
System.out.println(twoEditsDictionary(queries, dictionary));
}
}#include <vector>
#include <string>
#include <unordered_set>
std::unordered_set<std::string> preprocessDictionary(const std::vector<std::string>& dictionary) {
std::unordered_set<std::string> edited_words;
for (const auto& d : dictionary) {
int n = d.size();
// Try changing two characters at a time
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
for (char ch1 = 'a'; ch1 <= 'z'; ++ch1) {
for (char ch2 = 'a'; ch2 <= 'z'; ++ch2) {
std::string new_word = d;
new_word[i] = ch1;
new_word[j] = ch2;
edited_words.insert(new_word);
}
}
}
}
}
return edited_words;
}
std::vector<std::string> twoEditsDictionary(std::vector<std::string>& queries, std::vector<std::string>& dictionary) {
auto preprocessed = preprocessDictionary(dictionary);
std::vector<std::string> result;
for (const auto& q : queries) {
if (preprocessed.find(q) != preprocessed.end()) {
result.push_back(q);
}
}
return result;
}
// Example usage
// int main() { // ... }function preprocessDictionary(dictionary) {
const editedWords = new Set();
for (let d of dictionary) {
let n = d.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let ch1 = 97; ch1 <= 122; ch1++) {
for (let ch2 = 97; ch2 <= 122; ch2++) {
let newWord = d.split('');
newWord[i] = String.fromCharCode(ch1);
newWord[j] = String.fromCharCode(ch2);
editedWords.add(newWord.join(''));
}
}
}
}
}
return editedWords;
}
function twoEditsDictionary(queries, dictionary) {
const editedWords = preprocessDictionary(dictionary);
return queries.filter(q => editedWords.has(q));
}
// Example usage:
const queries = ["word", "note", "ants", "wood"];
const dictionary = ["wood", "joke", "moat"];
console.log(twoEditsDictionary(queries, dictionary));#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define MAX_WORDS 100
#define WORD_LEN 100
void addEditedWords(char* d, char editedWords[MAX_WORDS * 26 * 26][WORD_LEN], int* count) {
int n = strlen(d);
char newWord[WORD_LEN];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (char ch1 = 'a'; ch1 <= 'z'; ch1++) {
for (char ch2 = 'a'; ch2 <= 'z'; ch2++) {
strcpy(newWord, d);
newWord[i] = ch1;
newWord[j] = ch2;
if (*count < MAX_WORDS * 26 * 26) {
strcpy(editedWords[*count], newWord);
(*count)++;
}
}
}
}
}
}
bool existsInEditedWords(char* q, char editedWords[MAX_WORDS * 26 * 26][WORD_LEN], int count) {
for (int i = 0; i < count; i++) {
if (strcmp(q, editedWords[i]) == 0) return true;
}
return false;
}
void twoEditsDictionary(char queries[][WORD_LEN], int q_size, char dictionary[][WORD_LEN], int d_size, char result[][WORD_LEN], int* res_size) {
char editedWords[MAX_WORDS * 26 * 26][WORD_LEN];
int editedCount = 0;
for (int di = 0; di < d_size; ++di) {
addEditedWords(dictionary[di], editedWords, &editedCount);
}
*res_size = 0;
for (int qi = 0; qi < q_size; ++qi) {
if (existsInEditedWords(queries[qi], editedWords, editedCount)) {
strcpy(result[*res_size], queries[qi]);
(*res_size)++;
}
}
}
// Example usage
int main() {
char queries[4][WORD_LEN] = {"word", "note", "ants", "wood"};
char dictionary[3][WORD_LEN] = {"wood", "joke", "moat"};
char result[4][WORD_LEN];
int res_size;
twoEditsDictionary(queries, 4, dictionary, 3, result, &res_size);
for (int i = 0; i < res_size; ++i) {
printf("%s\n", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string[] queries = { "word", "note", "ants", "wood" };
string[] dictionary = { "wood", "joke", "moat" };
var result = TwoEditsDictionary(queries, dictionary);
Console.WriteLine(string.Join(", ", result));
}
static HashSet<string> PreprocessDictionary(string[] dictionary)
{
var editedWords = new HashSet<string>();
foreach (var d in dictionary)
{
int n = d.Length;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (char ch1 = 'a'; ch1 <= 'z'; ch1++)
{
for (char ch2 = 'a'; ch2 <= 'z'; ch2++)
{
char[] newWord = d.ToCharArray();
newWord[i] = ch1;
newWord[j] = ch2;
editedWords.Add(new string(newWord));
}
}
}
}
}
return editedWords;
}
static List<string> TwoEditsDictionary(string[] queries, string[] dictionary)
{
var preprocessed = PreprocessDictionary(dictionary);
var result = new List<string>();
foreach (var q in queries)
{
if (preprocessed.Contains(q))
{
result.Add(q);
}
}
return result;
}
}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.
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.
function twoEditWords(queries: string[], dictionary: string[]): string[] {
const n = queries[0].length;
return queries.filter(s => {
for (const t of dictionary) {
let diff = 0;
for (let i = 0; i < n; ++i) {
if (s[i] !== t[i]) {
++diff;
}
}
if (diff < 3) {
return true;
}
}
return false;
});
}func twoEditWords(queries []string, dictionary []string) (ans []string) {
for _, s := range queries {
for _, t := range dictionary {
cnt := 0
for i := range s {
if s[i] != t[i] {
cnt++
}
}
if cnt < 3 {
ans = append(ans, s)
break
}
}
}
return
}impl Solution {
pub fn two_edit_words(queries: Vec<String>, dictionary: Vec<String>) -> Vec<String> {
queries
.into_iter()
.filter(|s| {
dictionary
.iter()
.any(|t| s.chars().zip(t.chars()).filter(|&(a, b)| a != b).count() < 3)
})
.collect()
}
}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 | – |
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 |
Frequently asked questions
Is Words Within Two Edits of Dictionary easy or hard?
Words Within Two Edits of Dictionary is rated Medium because the brute-force logic is straightforward but recognizing the constraint that only substitutions matter requires careful observation. Optimizing with preprocessing or hashing adds another layer of algorithmic thinking.
Words Within Two Edits of Dictionary Python/Java solution
In Python or Java, iterate through each query and compare it with dictionary words character-by-character while counting mismatches. Break the loop once mismatches exceed two. If any dictionary word stays within the two-edit limit, append the query to the result list.
How to solve Words Within Two Edits of Dictionary in O(n)?
Strict O(n) is not typical because every query may need to compare against multiple dictionary words. However, preprocessing dictionary patterns with up to two wildcard positions allows faster lookups. This approach runs in about O(D * K^2 + Q * K^2) using hash sets, reducing repeated comparisons.
What is the best approach for Words Within Two Edits of Dictionary?
The most practical approach is scanning each query against every dictionary word while counting mismatched characters. Because all strings have the same length, the problem reduces to computing a Hamming distance and stopping once mismatches exceed two. This runs in O(Q * D * K) time and O(1) space and is typically the expected interview solution.
Is Words Within Two Edits of Dictionary asked at Google/Amazon/Meta?
String comparison and edit-distance style problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of Hamming distance, early termination optimizations, and hash-based preprocessing techniques.
What data structure is used in Words Within Two Edits of Dictionary?
The basic solution mainly uses arrays and string iteration. The optimized approach adds a hash set or hash map to store wildcard patterns derived from dictionary words, enabling constant-time pattern lookups.
What is the time complexity of Words Within Two Edits of Dictionary?
The direct comparison approach runs in O(Q * D * K), where Q is the number of queries, D is the number of dictionary words, and K is the word length. Each query may compare with every dictionary entry while scanning up to K characters. The space complexity is O(1) aside from the output list.