Words Within Two Edits Of Dictionary - Leetcode Solution

Problem Statement:

Given a dictionary, a method to do a lookup in the dictionary and a string named 'str'. Find and list all words in the dictionary that are less than or equal to two edits away from the string 'str'.

A word is considered to be less than or equal to two edits away from the string 'str' if:

1. One character can be added, removed or replaced in the word to make it the same as 'str' or
2. Two characters in the word can be swapped to make it the same as 'str'

Solution:

To solve this problem, let's first generate all possible words using the given string by performing the following operations:

1. Add a character at any position in the given string (n+1 words can be generated for n length string).
2. Remove a character from any position in the given string (n words can be generated for n length string).
3. Replace a character at any position in the given string (26*n words can be generated for n length string).

After generating all possible words, we can check which of them are present in the dictionary.

We can use a Trie data structure to store the words in the dictionary as it allows for efficient prefix searches and avoids the need to generate all possible substrings.

Once the trie is constructed, we can perform a DFS search to find all words within two edits of the given string.

The DFS search can be performed by starting with the given string and checking each possible character replacement, addition, removal, and swap that can be made. For each of these operations, we generate a new word and check if it is present in the Trie.

If a word is present in the Trie, we add it to our result set. We also repeat the same operation recursively on the newly generated word to check for any further possible words.

The time complexity of this approach is O(26^k) where k is the length of the given string. However, due to the use of Trie, the actual running time is much less.

Code:

Here is the python code to implement the above solution:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        current = self.root
        for ch in word:
            if ch not in current.children:
                current.children[ch] = TrieNode()
            current = current.children[ch]
        current.is_word = True

    def search_word(self, word):
        current = self.root
        for ch in word:
            if ch not in current.children:
                return False
            current = current.children[ch]
        return current.is_word

class Solution:
    def get_all_words(self, word):
        words = set()
        # Add a character
        for i in range(len(word) + 1):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + ch + word[i:]
                words.add(new_word)
        # Remove a character
        for i in range(len(word)):
            new_word = word[:i] + word[i+1:]
            words.add(new_word)
        # Replace a character
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + ch + word[i+1:]
                words.add(new_word)
        return words

    def dfs(self, word, trie, distance, visited, result):
        if distance > 2:
            return

        if trie.search_word(word):
            result.add(word)

        visited[word] = True

        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                # Word replacement
                if ch != word[i]:
                    new_word = word[:i] + ch + word[i+1:]
                    if new_word not in visited:
                        self.dfs(new_word, trie, distance + 1, visited, result)

                # Word addition
                new_word = word[:i] + ch + word[i:]
                if new_word not in visited:
                    self.dfs(new_word, trie, distance + 1, visited, result)

                # Word removal
                new_word = word[:i] + word[i+1:]
                if new_word not in visited:
                    self.dfs(new_word, trie, distance + 1, visited, result)

                # Word swap
                if i < len(word) - 1 and ch != word[i + 1]:
                    new_word = word[:i] + word[i+1] + ch + word[i+2:]
                    if new_word not in visited:
                        self.dfs(new_word, trie, distance + 1, visited, result)

        visited.pop(word)

    def findWords(self, dictionary, word):
        trie = Trie()
        for w in dictionary:
            trie.add_word(w)

        result = set()
        visited = {}
        self.dfs(word, trie, 0, visited, result)

        return list(result)

Test Cases:

Here are a few test cases to check the correctness of the solution:

dictionary = ["hello", "world", "leetcode", "goodbye"]
word = "hell"
assert Solution().findWords(dictionary, word) == ['hello', 'hell']

dictionary = ["hello", "world", "leetcode", "goodbye"]
word = "leetcodd"
assert Solution().findWords(dictionary, word) == ['leetcode']

dictionary = ["hello", "world", "leetcode", "goodbye"]
word = "leetcode"
assert sorted(Solution().findWords(dictionary, word)) == sorted(["leetcode", "leetcodd", "leetcede"])

dictionary = ["hello", "world", "leetcode", "goodbye"]
word = "leeecodd"
assert Solution().findWords(dictionary, word) == []

Conclusion:

In this problem, we have learned how to find all possible words that are less than or equal to two edits away from the given string. We have used a Trie data structure to store the words in the dictionary, and a DFS search to generate all possible words and check if they are present in the Trie. The time complexity of this approach is O(26^k) where k is the length of the given string.

1