Words Within Two Edits of Dictionary

Medium

Asked by:

10 views

Topics:

ArraysStringsTwo Pointers

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.

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- 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: []
Explanation:
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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the words in the input dictionary and the query words contain characters other than lowercase English letters?
What is the maximum length of a word in the dictionary and the query words? Are there any limits to the number of words in the dictionary or the query list?
If a query word is within two edits of multiple dictionary words, should I return all of them, and if so, is the order of returned words significant?
Is an empty dictionary a valid input? If so, what should the output be?
What constitutes an 'edit'? Is it only insertions, deletions, and substitutions, or do transpositions (swapping adjacent characters) also count?

Brute Force Solution

Approach

We need to find words from a list that are very similar to words in a dictionary. The brute force method checks every word in our list against every word in the dictionary to see how similar they are.

Here's how the algorithm would work step-by-step:

Take the first word from the list we need to check.
Compare it to the first word in the dictionary.
Count how many letters are different between these two words.
If the number of different letters is two or less, mark the word from the list as similar.
Compare the list word to the next word in the dictionary, and repeat the counting and marking process.
Keep going through the entire dictionary, comparing the list word to each dictionary word.
Once we've compared the list word to every word in the dictionary, we know if it's similar to any of them.
Move to the next word in the list we need to check, and repeat the entire process of comparing it to every word in the dictionary.
Continue until every word in the list has been compared to every word in the dictionary.

Code Implementation

def words_within_two_edits_of_dictionary(query_words, dictionary_words):
    similar_words = []

    for query_word in query_words:
        is_similar = False

        for dictionary_word in dictionary_words:
            # Only compare words of the same length
            if len(query_word) == len(dictionary_word):
                difference_count = 0

                for index in range(len(query_word)):
                    if query_word[index] != dictionary_word[index]:
                        difference_count += 1

                # Check if edit distance is within the limit
                if difference_count <= 2:
                    is_similar = True

                    # No need to check other dictionary words if match found
                    break

        # Add word to result if similar
        if is_similar:
            similar_words.append(query_word)

    return similar_words

Big(O) Analysis

Time Complexity

O(m*n*k) – The outer loop iterates through each word in the input query list of size m. The inner loop iterates through each word in the dictionary of size n. Inside the inner loop, we compare the current query word to the current dictionary word, which takes O(k) time where k is the length of the strings being compared (assuming the strings have similar length and we iterate character by character). Therefore, the total time complexity is O(m*n*k).

Space Complexity

O(1) – The provided algorithm's space complexity is O(1) because it operates in place. It only uses a fixed number of variables, such as counters for different letters. The number of variables doesn't depend on the size of the dictionary or the input list of words. Therefore, the auxiliary space used remains constant, regardless of the input size N (where N is the total number of words in the dictionary and input list).

Optimal Solution

Approach

To efficiently find dictionary words within two edits of each query word, we pre-process the dictionary to create a lookup structure. This allows us to quickly check how many edits are needed to transform each query word into a potential match, avoiding redundant calculations.

Here's how the algorithm would work step-by-step:

First, we need to get the dictionary ready for fast comparisons. We do this by creating a way to quickly find which dictionary words are similar to other words.
For each word we're searching for, we generate all possible words that are one or two edits away from it. This involves changing letters, adding letters, or removing letters.
Now, instead of checking every dictionary word individually, we use the list of edited words we just created. We check if any of the edited words are in our pre-processed dictionary.
If an edited word is found in the dictionary, then the original dictionary word is considered to be at most two edits away from our search word.
We repeat this process for each word we are searching for, collecting all the dictionary words that are two edits away.
Finally, we return the list of dictionary words we found.

Code Implementation

def words_within_two_edits(query_words, dictionary):
    result = []
    dictionary_set = set(dictionary)

    for query_word in query_words:
        # Generate words within two edits
        close_matches = find_close_matches(query_word, dictionary_set)
        result.append(close_matches)

    return result

def find_close_matches(query_word, dictionary_set):
    close_words = []
    queue = [(query_word, 0)]
    visited = {query_word}

    while queue:
        current_word, edit_distance = queue.pop(0)

        if current_word in dictionary_set:
            close_words.append(current_word)

        # Only explore further if within the edit distance limit
        if edit_distance < 2:
            for next_word in generate_one_edit_words(current_word):
                if next_word not in visited:
                    queue.append((next_word, edit_distance + 1))
                    visited.add(next_word)

    return list(set(close_words))

def generate_one_edit_words(word):
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    one_edit_words = set()

    # Deletions
    for i in range(len(word)): 
        one_edit_words.add(word[:i] + word[i+1:])

    # Insertions
    for i in range(len(word) + 1):
        for char in alphabet:
            one_edit_words.add(word[:i] + char + word[i:])

    # Substitutions
    for i in range(len(word)):  
        for char in alphabet:
            one_edit_words.add(word[:i] + char + word[i+1:])

    return one_edit_words

Big(O) Analysis

Time Complexity

O(M * (N + A^L + D)) – Let M be the number of query words, N be the number of dictionary words, A be the size of the alphabet, L be the maximum length of a word, and D be the average time to check if a word exists in the dictionary (assuming a hash set, D would be O(1) on average). For each of the M query words, we generate all possible words that are one or two edits away, taking O(A^L) time in the worst case. Then, we iterate through the pre-processed dictionary, which takes O(N) time initially. Finally, checking if each generated word is in the dictionary takes O(D) time per generated word. Thus the overall time complexity is O(M * (N + A^L + D)).

Space Complexity

O(N * M^26) – The solution pre-processes the dictionary but the explanation doesn't provide enough detail on how this is done to assess its space complexity. The major space consumer comes from generating all possible words within one or two edits of each query word. In the worst case, for a query word of length M, generating all possible one or two edit words will result in a large number of combinations which can be approximated as O(M^26) where M is the length of the longest word, considering substitutions, insertions, and deletions against the 26 letters of the alphabet. This process needs to be repeated for each of the N query words. Thus, the overall auxiliary space is bounded by the space required to store the generated words for all query words, leading to a space complexity of O(N * M^26).

Edge Cases

Case	How to Handle
Null or empty dictionary	Return an empty list since no words from queries can be within two edits of any word in an empty dictionary.
Null or empty queries list	Return an empty list as there are no query words to check against the dictionary.
Empty string in dictionary or queries	Handle empty strings by considering any non-empty string to be at least one edit away; if both are empty, they are 0 edits away, so equality checks should account for this.
Dictionary words with significantly varying lengths compared to query words	Implement a length check before the edit distance calculation; if length difference exceeds 2, skip edit distance calculation to improve efficiency.
Dictionary and queries containing identical words	Ensure that identical words are considered to be within two edits of themselves by handling 0 edit differences correctly.
Very large dictionary and queries list impacting memory usage	Optimize memory by using iterators or generators when processing large lists to avoid loading everything into memory at once.
Words containing non-ASCII characters	Ensure the edit distance calculation handles Unicode or other character encodings correctly (e.g., UTF-8).
Large Levenshtein distance calculations leading to potential performance bottleneck	Consider implementing early stopping conditions in the Levenshtein distance calculation if the distance exceeds 2, to avoid unnecessary computations.

Null or empty dictionary

How to Handle:

Return an empty list since no words from queries can be within two edits of any word in an empty dictionary.

Null or empty queries list

How to Handle:

Return an empty list as there are no query words to check against the dictionary.

Empty string in dictionary or queries

How to Handle:

Handle empty strings by considering any non-empty string to be at least one edit away; if both are empty, they are 0 edits away, so equality checks should account for this.

Dictionary words with significantly varying lengths compared to query words

How to Handle:

Implement a length check before the edit distance calculation; if length difference exceeds 2, skip edit distance calculation to improve efficiency.

Dictionary and queries containing identical words

How to Handle:

Ensure that identical words are considered to be within two edits of themselves by handling 0 edit differences correctly.

Very large dictionary and queries list impacting memory usage

How to Handle:

Optimize memory by using iterators or generators when processing large lists to avoid loading everything into memory at once.

Words containing non-ASCII characters

How to Handle:

Ensure the edit distance calculation handles Unicode or other character encodings correctly (e.g., UTF-8).

Large Levenshtein distance calculations leading to potential performance bottleneck

How to Handle:

Consider implementing early stopping conditions in the Levenshtein distance calculation if the distance exceeds 2, to avoid unnecessary computations.