We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Words Within Two Edits of Dictionary

Number: 2550

Difficulty: Medium

Paid? No

Companies: Google, Meta

Problem Description

Given two arrays of strings, queries and dictionary, determine which words in queries can be transformed into at least one word in dictionary by performing at most two single-letter edits. Each edit consists of changing a letter to any other letter. All words are of the same length. The answer should list the qualifying query words in the same order they appear.

Key Insights

  • For each query word, check every dictionary word to count the number of differing positions.
  • A query word is valid if there exists at least one dictionary word with at most two differing characters.
  • The problem can be solved using a brute-force approach since the maximum size of queries and dictionary, along with word length, is small.
  • Early stopping during letter comparisons can improve performance by breaking out as soon as the edit count exceeds two.

Space and Time Complexity

Time Complexity: O(q * d * n), where q is the number of queries, d is the number of dictionary words, and n is the length of each word. Space Complexity: O(1) additional space (excluding the space for the output list).

Solution

The approach involves iterating through each word in the queries array. For each query word, we iterate through every word in the dictionary and compare them character by character to count the differences. If the number of differences is two or fewer for any dictionary word, the query word is added to the result list. By using early termination in the character comparison loop, the algorithm improves efficiency when a word exceeds the allowed edit threshold. This brute-force method is acceptable given the constraints.

Code Solutions

def two_edits_away(queries, dictionary):
    valid_words = []  # List to hold valid query words
    # Iterate through every query word
    for word in queries:
        # Compare query word with each dictionary word
        for dict_word in dictionary:
            # Count number of positions with different characters
            differences = sum(1 for q_char, d_char in zip(word, dict_word) if q_char != d_char)
            # If edit count is within two, mark word as valid
            if differences <= 2:
                valid_words.append(word)
                break  # Stop checking other dictionary words for this query
    return valid_words

# Example usage:
queries = ["word", "note", "ants", "wood"]
dictionary = ["wood", "joke", "moat"]
print(two_edits_away(queries, dictionary))  # Output: ["word", "note", "wood"]
← Back to All Questions