Problem Statement in English

You’re given two string arrays queries and dictionary. You have to return a list of all strings in queries that are within 2 edits of any string in dictionary. An edit is defined as changing a single character in the string.

Approach

You just need to brute force through all the queries and for each query, check if it is within 2 edits of any string in the dictionary.

To check if two strings are within 2 edits, you can iterate through both strings and count the number of positions where they differ.

If the count is less than or equal to 2, then the strings are within 2 edits.

And we’re done!

Solution in Python


class Solution:
    def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
        res = []
        for q in queries:
            for d in dictionary:
                mistakes = 0

                for i in range(len(q)):
                    if q[i] != d[i]:
                        mistakes += 1
                    
                    if mistakes > 2:
                        break
                else:
                    res.append(q)
                    break

        return res

Complexity

  • Time: $O(m \cdot n \cdot k)$
    Where m is the length of queries, n is the length of dictionary and k is the length of each word. Since we have to compare each query with each word in the dictionary and each comparison takes O(k) time.

  • Space: $O(m)$
    Since we store the result in a list which can have at most m elements.

And we are done.