LeetCode 2452 - Words Within Two Edits of Dictionary

Difficulty: 🟡 Medium
Topics: Array, String, Trie

Solution

Problem Understanding

The problem asks us to identify words in the queries list that can be transformed into a word in the dictionary list with at most two character edits. Each edit consists of changing a single character to another lowercase English letter. The words in both arrays are guaranteed to have the same length, which simplifies comparison because we do not need to handle insertions or deletions, only substitutions.

The inputs are:

queries: a list of strings representing candidate words.
dictionary: a list of strings representing valid words we want to match against.

The expected output is a list of strings from queries that can become a word in dictionary using 0, 1, or 2 edits, preserving the order in which they appear in queries.

Constraints tell us:

Both arrays have up to 100 elements, and each word has length up to 100. This means a brute-force comparison of each query with each dictionary word is feasible, since 100 * 100 = 10,000 comparisons in the worst case. Each comparison involves at most 100 character checks.
All strings consist of lowercase letters, so character-level comparison is straightforward.

Important edge cases include:

Words that are already in the dictionary (0 edits needed).
Words that differ by exactly 1 or 2 characters.
Words that require more than 2 edits and should not be included.
Minimum input sizes (length 1 strings or single-element lists).

Approaches

Brute-Force Approach

The brute-force approach compares each query against every dictionary word. For each pair, count how many characters differ. If the number of differing characters is 0, 1, or 2, include the query in the result. This approach is correct because it exhaustively checks all possible matches but could be slow if input sizes were larger.

Key Insight for Optimal Approach

Given the constraints, the brute-force approach is already efficient. No additional data structure is necessary. The key insight is that we only need a simple character-by-character comparison and an early exit once more than 2 differences are detected. This avoids unnecessary checks and slightly improves runtime.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(Q * D * n)	O(Q)	Compare each query with each dictionary word; n is the word length
Optimal	O(Q * D * n)	O(Q)	Early exit after 3 mismatches reduces constant factor, otherwise same as brute force

Algorithm Walkthrough

Initialize an empty list result to store valid queries.
Iterate over each word query in queries.
For each query, iterate over each word word in dictionary.
Initialize a counter diff to 0.
Compare characters at each index between query and word. Increment diff for every mismatch.
If at any point diff exceeds 2, break the inner loop early since this dictionary word cannot match.
If after comparing all characters diff is 2 or less, append query to result and break to the next query.
Return result after all queries are processed.

Why it works: The algorithm checks every query against every dictionary word for up to two allowed edits. Early termination ensures efficiency. Since every query is compared with all possible matches, no valid word is missed.

Python Solution

from typing import List

class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        result = []
        for query in queries:
            for word in dictionary:
                diff = 0
                for c1, c2 in zip(query, word):
                    if c1 != c2:
                        diff += 1
                        if diff > 2:
                            break
                if diff <= 2:
                    result.append(query)
                    break
        return result

Implementation Explanation: We iterate through each query and each dictionary word, counting mismatched characters. Using zip simplifies character-by-character comparison. We immediately stop counting if mismatches exceed 2 to save unnecessary computation. Once a match is found, the query is added to result and we continue to the next query.

Go Solution

func twoEditWords(queries []string, dictionary []string) []string {
    var result []string
    for _, query := range queries {
        for _, word := range dictionary {
            diff := 0
            for i := 0; i < len(query); i++ {
                if query[i] != word[i] {
                    diff++
                    if diff > 2 {
                        break
                    }
                }
            }
            if diff <= 2 {
                result = append(result, query)
                break
            }
        }
    }
    return result
}

Go-specific Notes: The Go version uses a standard for loop for character comparison, since Go strings are byte slices. append is used to build the result slice dynamically. There is no need to handle nil slices as the input constraints guarantee non-empty lists.

Worked Examples

Example 1:

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

Step through query = "word":

Compare with "wood": differences = 1 ('r' -> 'o'), append "word".
"note": compare with "joke": differences = 2 ('n' -> 'j', 't' -> 'k'), append "note".
"ants": compare with all dictionary words, differences exceed 2, skip.
"wood": matches "wood" exactly, append "wood".

Result = ["word","note","wood"].

Example 2:

queries = ["yes"]
dictionary = ["not"]

"yes" vs "not": differences = 3, exceeds 2, skip.

Result = [].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(Q * D * n)	Q queries, D dictionary words, n characters per word. Worst case all comparisons needed.
Space	O(Q)	Result list storing matching queries.

The early exit reduces constants but does not change the asymptotic complexity.

Test Cases

# Basic examples
assert Solution().twoEditWords(["word","note","ants","wood"], ["wood","joke","moat"]) == ["word","note","wood"]  # Example 1
assert Solution().twoEditWords(["yes"], ["not"]) == []  # Example 2

# Edge cases
assert Solution().twoEditWords(["a"], ["a"]) == ["a"]  # single character, exact match
assert Solution().twoEditWords(["a"], ["b"]) == ["a"]  # single character, one edit
assert Solution().twoEditWords(["abc"], ["xyz"]) == []  # three edits needed, should not match
assert Solution().twoEditWords(["abc","abd","xyz"], ["abc","abx"]) == ["abc","abd"]  # multiple matches
assert Solution().twoEditWords([], ["abc"]) == []  # empty queries
assert Solution().twoEditWords(["abc"], []) == []  # empty dictionary

Test	Why
["word","note","ants","wood"], ["wood","joke","moat"]	Standard example with 0-2 edits
["yes"], ["not"]	No matches possible
["a"], ["a"]	Minimum length, exact match
["a"], ["b"]	Minimum length, one edit
["abc"], ["xyz"]	Exceeds 2 edits
["abc","abd","xyz"], ["abc","abx"]	Multiple queries with some matches
[] , ["abc"]	Empty query list
["abc"], []	Empty dictionary

Edge Cases

Queries with exact matches in the dictionary: These require 0 edits. Implementation correctly identifies them without additional logic because the difference counter will be zero, which is ≤ 2.
Queries that differ by exactly 2 characters: These are borderline cases. The algorithm handles them by counting mismatches, and as long as the count is ≤ 2, the word is included in the result.
Queries requiring more than 2 edits: Such words should be excluded. The early exit mechanism ensures that once diff > 2, the inner loop breaks and the query is not added.
Single-character words: Since words can be length 1, we must correctly handle these, including zero or one edits. The solution works because it compares character-by-character and the constraints allow n = 1.
Empty lists: The algorithm handles empty queries or dictionary gracefully, returning an empty result without error.