#2452

Medium

LeetCode Problem Workspace

Words Within Two Edits of Dictionary

Identify all words in queries that can match dictionary entries with at most two character changes efficiently using array and string operations.

array string trie

Problem Statement

You are given two arrays of lowercase strings, queries and dictionary, where every string in both arrays has the same length. Your task is to identify which words from queries can be transformed into any word in dictionary by changing at most two letters.

Return a list of all matching words from queries in the original order they appear. A word is valid if it can equal any dictionary word after zero, one, or two character edits.

Examples

Example 1

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

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

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: []

Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
All queries[i] and dictionary[j] are composed of lowercase English letters.

Solution Approach

Brute-Force Character Comparison

Iterate through each word in queries and compare it to each word in the dictionary. Count the number of differing characters. If the differences are at most two, add the query word to the result. This method is simple and effective for small input sizes.

Optimize with Early Termination

While comparing characters between a query and a dictionary word, stop checking further if more than two differences are found. This reduces unnecessary comparisons and improves performance on larger arrays.

Trie-Based Approach for Faster Lookup

Construct a Trie from the dictionary words. Then, for each query, traverse the Trie allowing at most two mismatches. This approach avoids full pairwise comparisons and is useful when dictionary and query sizes are larger or lengths of words are significant.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on whether brute-force or Trie is used: brute-force is O(Q D N) for Q queries, D dictionary words, and word length N. Trie approach reduces redundant comparisons but may require extra space for the Trie nodes, giving space complexity proportional to total characters in the dictionary.

What Interviewers Usually Probe

Watch for queries that are already in the dictionary to avoid unnecessary edits.
Check that edits do not exceed two; counting differences incorrectly can fail test cases.
Consider word length constraints to avoid index errors when comparing characters.

Common Pitfalls or Variants

Common pitfalls

Failing to count zero-edit matches when a query word exactly matches a dictionary word.
Stopping comparisons too early or too late, leading to incorrect inclusion or exclusion.
Assuming all words have unique lengths; ensure all queries and dictionary words have the same length.

Follow-up variants

Allowing up to k edits instead of exactly two edits for a more general version.
Returning the number of edits needed for each matching query instead of just the words.
Checking for subsequence edits instead of single-character replacements.

FAQ

What is the best way to check if a query word is within two edits of a dictionary word?

Compare the query word to each dictionary word character by character, counting mismatches, and accept it if differences are two or fewer.

Can I optimize beyond brute-force for this problem?

Yes, using a Trie allows efficient traversal and mismatch tracking, reducing redundant pairwise checks for large dictionaries.

Does the order of returned words matter?

Yes, the output list should preserve the original order of words in the queries array.

Do I need to handle words of different lengths?

No, all query and dictionary words are guaranteed to have the same length according to the problem constraints.

What pattern does this problem represent in GhostInterview?

This is an 'Array plus String' pattern where each query is matched against multiple strings with limited edits allowed.

terminal

Solution

Solution 1: Brute Force Enumeration

We directly traverse each word $s$ in the array $\textit{queries}$, and then traverse each word $t$ in the array $\textit{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$.

1

2

3

4

5

6

7

8

9

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        ans = []
        for s in queries:
            for t in dictionary:
                if sum(a != b for a, b in zip(s, t)) < 3:
                    ans.append(s)
                    break
        return ans

Continue Practicing

#2416 sum of prefix scores of strings #2227 encrypt and decrypt strings #2707 extra characters in a string