Words Within Two Edits of Dictionary - Practice Coding Problems

Words Within Two Edits of Dictionary - 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.

Input & Output

Example 1 — Basic Case

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

› Output: ["word","note","wood"]

💡 Note: "word" → "wood" (1 edit: r→o), "note" → "joke" (1 edit: n→j), "wood" → "wood" (0 edits), "ants" needs 3 edits minimum

Example 2 — Two Edits Required

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

› Output: []

💡 Note: "yes" → "not" requires 3 edits (y→n, e→o, s→t), which exceeds the maximum of 2

Example 3 — Multiple Matches

$ Input: queries = ["leet","code"], dictionary = ["lead","cool"]

› Output: ["leet","code"]

💡 Note: "leet" → "lead" (2 edits: e→a, t→d), "code" → "cool" (2 edits: d→l, e→l)

Constraints

1 ≤ queries.length, dictionary.length ≤ 100
1 ≤ queries[i].length, dictionary[i].length ≤ 100
queries[i] and dictionary[i] consist of only lowercase English letters
All queries[i] and dictionary[i] have the same length

Visualization

Tap to expand

Understanding the Visualization

Input

Queries: ["word","note","ants"] and Dictionary: ["wood","joke","moat"]

Process

Compare each query with all dictionary words, counting character differences

Output

Return queries that match within 2 edits: ["word","note"]

Key Takeaway

🎯 Key Insight: Only count character differences - if more than 2, the word cannot match within the limit

Asked in

G Google 25 f Facebook 18

The key insight is that we only need to count character differences between words. The most efficient approach is brute force with early termination - compare each query word with every dictionary word and stop counting when differences exceed 2. Time: O(n*m*k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set for Dictionary Lookup	O(nk²26²)	O(m*k)	Use hash set for O(1) dictionary lookups instead of linear search
Early Termination Optimization	O(nmk)	O(1)	Same approach but stop counting differences when they exceed 2
Brute Force Comparison	O(nmk)	O(1)	Compare each query word with every dictionary word character by character

Hash Set for Dictionary Lookup — Algorithm Steps

Step 1: Convert dictionary to hash set
Step 2: For each query, generate possible edits
Step 3: Check if any edited version exists in set
Step 4: Add query to result if match found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Convert dictionary to hash set for O(1) lookup

Generate Edits

Create all possible 1 and 2 character edits

Check Existence

Look up each edited version in hash set

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_LEN 100

typedef struct {
    char words[MAX_WORDS][MAX_LEN];
    int size;
} HashSet;

bool contains(HashSet* set, char* word) {
    for (int i = 0; i < set->size; i++) {
        if (strcmp(set->words[i], word) == 0) {
            return true;
        }
    }
    return false;
}

char** solution(char** queries, int queriesSize, char** dictionary, int dictSize, int* returnSize) {
    HashSet dictSet = {0};
    for (int i = 0; i < dictSize; i++) {
        strcpy(dictSet.words[dictSet.size++], dictionary[i]);
    }
    
    char** result = (char**)malloc(queriesSize * sizeof(char*));
    *returnSize = 0;
    
    for (int i = 0; i < queriesSize; i++) {
        bool found = false;
        int len = strlen(queries[i]);
        
        // Check 0 edits
        if (contains(&dictSet, queries[i])) {
            result[*returnSize] = (char*)malloc((len + 1) * sizeof(char));
            strcpy(result[*returnSize], queries[i]);
            (*returnSize)++;
            continue;
        }
        
        // Check 1 edit
        char modified[MAX_LEN];
        for (int j = 0; j < len && !found; j++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != queries[i][j]) {
                    strcpy(modified, queries[i]);
                    modified[j] = c;
                    if (contains(&dictSet, modified)) {
                        result[*returnSize] = (char*)malloc((len + 1) * sizeof(char));
                        strcpy(result[*returnSize], queries[i]);
                        (*returnSize)++;
                        found = true;
                        break;
                    }
                }
            }
        }
    }
    
    return result;
}

int main() {
    char* queries[] = {"word", "note", "ants", "wood"};
    char* dictionary[] = {"wood", "joke", "moat"};
    
    int returnSize;
    char** result = solution(queries, 4, dictionary, 3, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*k²*26²)

n queries × k² positions for 2 edits × 26² character combinations

✓ Linear Growth

Space Complexity

O(m*k)

Hash set storing m dictionary words of length k

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set for Dictionary Lookup — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler