Implement Magic Dictionary

Medium

Asked by:

16 views

Topics:

Strings

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

MagicDictionary() Initializes the object.
void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:

Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]

Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // return False
magicDictionary.search("hhllo"); // We can change the second 'h' to 'e' to match "hello" so we return True
magicDictionary.search("hell"); // return False
magicDictionary.search("leetcoded"); // return False

Constraints:

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lower-case English letters.
All the strings in dictionary are distinct.
1 <= searchWord.length <= 100
searchWord consists of only lower-case English letters.
buildDict will be called only once before search.
At most 100 calls will be made to search.

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 dictionary and the search word contain characters other than lowercase English letters?
What is the maximum length of a word in the dictionary, and what is the maximum length of the search word?
If multiple words in the dictionary are one edit distance away from the search word, should the `search` function return `true` if *any* such word exists?
If the dictionary is empty, what should the `search` function return?
Should I consider case sensitivity when comparing words?

Brute Force Solution

Approach

The magic dictionary problem asks us to see if a given word is similar to any word from a pre-defined dictionary. The brute force approach involves exhaustively comparing the given word to every word in the dictionary to see if they are only one character different.

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

For the dictionary creation, we just store all the words given to us.
When we need to search for a similar word, we take the word we are searching for and go through each word in our dictionary one by one.
For each dictionary word, we compare it to the search word. If they are different lengths, we skip it.
If they are the same length, we count how many characters are different between the two words.
If exactly one character is different, we have found a match and we can stop looking and return true.
If we go through the entire dictionary and don't find any matches, we return false.

Code Implementation

class MagicDictionary:
    def __init__(self):
        self.dictionary_words = []

    def buildDict(self, dictionary):
        self.dictionary_words = dictionary

    def search(self, search_word):
        for dictionary_word in self.dictionary_words:
            # Skip if words have different lengths
            if len(dictionary_word) != len(search_word):
                continue

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

            # Check if exactly one character is different
            if difference_count == 1:
                return True

        # No match found after checking all words
        return False

Big(O) Analysis

Time Complexity

O(n*m) – The dictionary creation takes O(n) time, where n is the number of words in the dictionary. The search function iterates through each word in the dictionary (n words). For each dictionary word, it compares it character by character with the search word, which takes O(m) time, where m is the length of the words. Therefore, the search operation has a time complexity of O(n*m), dominating the overall complexity. The total complexity is thus O(n*m).

Space Complexity

O(N) – The space complexity is determined by the storage of the dictionary words. The dictionary stores all N words provided as input. No other significant data structures are created, and the space used is primarily for storing the dictionary itself. Therefore, the auxiliary space grows linearly with the number of words in the dictionary.

Optimal Solution

Approach

The magic dictionary needs to quickly find words that are similar to a search word, differing by only one letter. Instead of checking every word in the dictionary against the search word, we can use a more organized approach. This involves pre-processing the dictionary to make lookups much faster.

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

First, when we build the dictionary, organize the words by their lengths. This means grouping all words of length 3 together, all words of length 4 together, and so on.
When searching, start by only considering words in the dictionary that have the same length as the search word.
For each word of the same length, compare it to the search word. Count how many letters are different.
If only one letter is different, then we have found a match, and return true.
If no words of the same length have only one letter difference, then return false.

Code Implementation

class MagicDictionary:

    def __init__(self):
        self.words_by_length = {}

    def buildDict(self, dictionary: list[str]) -> None:
        for word in dictionary:
            word_length = len(word)
            if word_length not in self.words_by_length:
                self.words_by_length[word_length] = []
            self.words_by_length[word_length].append(word)

    def search(self, search_word: str) -> bool:
        search_word_length = len(search_word)
        # Only check words of the same length
        if search_word_length not in self.words_by_length:
            return False

        for dictionary_word in self.words_by_length[search_word_length]:
            difference_count = 0

            for i in range(search_word_length):
                if search_word[i] != dictionary_word[i]:
                    difference_count += 1

            # Check if the difference is exactly one letter
            if difference_count == 1:
                return True

        # No match found
        return False

Big(O) Analysis

Time Complexity

O(N*L) – The buildDict operation iterates through each word in the input dictionary (N words) and stores it based on its length. This takes O(N) time. The search operation first identifies the list of words with the same length (L being the maximum length of words in the dictionary). Then, it iterates through each word in that list. For each word, it compares each of the letters with the search word, taking O(L) for each word comparison. Therefore, the search complexity is O(Number of words with the same length * L) which can be approximated as O(N*L) in the worst case if most words are of the same length. Thus search has an overall time complexity of O(N*L).

Space Complexity

O(N) – The primary auxiliary space usage comes from organizing the dictionary words by their lengths. This involves creating a data structure, likely a hash map or dictionary, where keys represent word lengths and values are lists of words with that length. In the worst case, all N words in the dictionary could have different lengths, requiring storage for all N words in this length-based organization. Therefore, the space complexity is O(N), where N is the number of words in the dictionary.

Edge Cases

Case	How to Handle
Empty dictionary or empty search word	Return false immediately since no match is possible.
Dictionary words with different lengths than search word	Skip these dictionary words as they can never be a valid one-edit distance match.
Dictionary contains duplicate words	Storing in a set eliminates duplicates, ensuring correct behavior.
Search word is very long	The one-edit-distance check scales linearly with search word length, so performance degrades gracefully.
Dictionary is extremely large	Consider using a Trie data structure to optimize the search for words with one-edit distance.
Search word is present in the dictionary	The code correctly distinguishes the same word as a non-valid match by enforcing a single difference for the match to be true.
Characters in the words are non-ASCII	The solution will work correctly as long as the language (e.g. Python) handles unicode characters in strings, provided we are comparing character to character.
Integer overflow from word length calculations	This is not applicable as we are dealing with string lengths and comparisons, not intensive numerical operations that would lead to overflow.

Empty dictionary or empty search word

How to Handle:

Return false immediately since no match is possible.

Dictionary words with different lengths than search word

How to Handle:

Skip these dictionary words as they can never be a valid one-edit distance match.

Dictionary contains duplicate words

How to Handle:

Storing in a set eliminates duplicates, ensuring correct behavior.

Search word is very long

How to Handle:

The one-edit-distance check scales linearly with search word length, so performance degrades gracefully.

Dictionary is extremely large

How to Handle:

Consider using a Trie data structure to optimize the search for words with one-edit distance.

Search word is present in the dictionary

How to Handle:

The code correctly distinguishes the same word as a non-valid match by enforcing a single difference for the match to be true.

Characters in the words are non-ASCII

How to Handle:

The solution will work correctly as long as the language (e.g. Python) handles unicode characters in strings, provided we are comparing character to character.

Integer overflow from word length calculations

How to Handle:

This is not applicable as we are dealing with string lengths and comparisons, not intensive numerical operations that would lead to overflow.