2452. Words Within Two Edits of Dictionary

Array
String

TIME

O(Q D N)

SPACE

O(1)

Intuition

Given small constraints (≤100 for all dimensions), brute force comparison works. For each query, check if any dictionary word differs by at most 2 characters.

Solution

def matches(q, d):
    diff = sum(c1 != c2 for c1, c2 in zip(q, d))
    return diff <= 2

result = []
for query in queries:
    if any(matches(query, word) for word in dictionary):
        result.append(query)

Optimization

Early termination: stop counting differences once we exceed 2.

def matches(q, d):
    diff = 0
    for c1, c2 in zip(q, d):
        if c1 != c2:
            diff += 1
            if diff > 2:
                return False
    return True

Complexity

Time: O(Q × D × N) where Q = queries, D = dictionary, N = word length
Space: O(1) extra (excluding output)

Edge Cases

Exact match (0 edits)
All queries match
No queries match
Single character words

Code

from typing import List


class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        """
        2452. Words Within Two Edits of Dictionary
        Time: O(Q * D * N)
        Space: O(1)
        """

        def matches(q: str, d: str) -> bool:
            diff = 0
            for c1, c2 in zip(q, d):
                if c1 != c2:
                    diff += 1
                    if diff > 2:
                        return False
            return True

        result = []
        for query in queries:
            if any(matches(query, word) for word in dictionary):
                result.append(query)

        return result

import java.util.*;

/**
 * 2452. Words Within Two Edits of Dictionary
 * Time: O(Q * D * N)
 * Space: O(1)
 */
class Solution {
    public List<String> twoEditWords(String[] queries, String[] dictionary) {
        List<String> result = new ArrayList<>();

        for (String query : queries) {
            for (String word : dictionary) {
                if (matches(query, word)) {
                    result.add(query);
                    break;
                }
            }
        }

        return result;
    }

    private boolean matches(String q, String d) {
        int diff = 0;
        for (int i = 0; i < q.length(); i++) {
            if (q.charAt(i) != d.charAt(i)) {
                diff++;
                if (diff > 2) {
                    return false;
                }
            }
        }
        return true;
    }
}