Implement Magic Dictionary

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:

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

## Magic Dictionary Implementation

This problem requires implementing a `MagicDictionary` class that can be initialized with a list of distinct words and then efficiently determine if a given `searchWord` can be matched to any word in the dictionary by changing exactly one character.

### Naive Approach

A straightforward but potentially inefficient approach is to iterate through the dictionary for each search query and compare each word with the `searchWord`. For each word in the dictionary, count the number of differing characters. If exactly one character differs, return `true`. This approach has a time complexity of O(N*M), where N is the number of words in the dictionary and M is the maximum length of a word.

```python
class MagicDictionary:

    def __init__(self):
        self.dictionary = []

    def buildDict(self, dictionary: list[str]) -> None:
        self.dictionary = dictionary

    def search(self, searchWord: str) -> bool:
        for word in self.dictionary:
            if len(word) != len(searchWord):
                continue
            diff_count = 0
            for i in range(len(word)):
                if word[i] != searchWord[i]:
                    diff_count += 1
            if diff_count == 1:
                return True
        return False

Optimal Approach

To improve the efficiency, we can use a hash map to store words grouped by their length. This will reduce the number of words we need to compare against. When searching, we only compare the searchWord against words in the dictionary that have the same length.

class MagicDictionary:

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

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

    def search(self, searchWord: str) -> bool:
        length = len(searchWord)
        if length not in self.word_map:
            return False

        for word in self.word_map[length]:
            diff_count = 0
            for i in range(length):
                if word[i] != searchWord[i]:
                    diff_count += 1
            if diff_count == 1:
                return True
        return False

Big(O) Run-time Analysis

• buildDict: O(N), where N is the number of words in the initial dictionary. We iterate through each word once to populate the hash map.
• search: In the worst case, O(M*K), where M is the length of the searchWord and K is the number of words in the dictionary that have the same length as searchWord. In the best case, O(1) if no words of the same length exist in the dictionary.

Big(O) Space Usage Analysis

• O(N), where N is the number of words in the dictionary. We store all words in the word_map.

Edge Cases

1. Empty Dictionary: If the dictionary is empty, the search method should always return false.
2. Empty Search Word: If the searchWord is empty, the search method should return false.
3. Words of Different Lengths: The search method should only compare words of the same length as the searchWord.
4. Search Word is Identical to a Dictionary Word: The search method should return false if the searchWord is exactly the same as a word in the dictionary, as it requires a change of one character.