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 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

## Magic Dictionary Problem

This problem involves designing a data structure to store a dictionary of words and efficiently search for words that differ from a given search word by exactly one character.

### Naive Solution

A simple, brute-force approach would be to iterate through each word in the dictionary and compare it to the search word. For each word, count the number of differing characters. If the count is exactly one, return `true`. Otherwise, continue iterating. If no such word is found, return `false`.

```python
class MagicDictionary:

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

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

    def search(self, searchWord: str) -> bool:
        for word in self.words:
            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 Solution: Using a Hash Map

To optimize the search process, we can use a hash map where keys are word lengths and values are lists of words with that length. This reduces the number of comparisons by only checking words of the same length as the search word. Further optimization involves generating all possible one-character variations of each dictionary word and storing them in a separate hash map.

class MagicDictionary:

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

    def buildDict(self, dictionary: List[str]) -> None:
        self.word_map = {}
        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 dictionary. We iterate through each word once.
• search: O(M * L), where M is the number of words in the dictionary that have the same length as the search word, and L is the length of the search word. In the worst case, M could be equal to N (all words have the same length), but on average, M will be smaller. The character comparison within the loop takes O(L) time.

Big(O) Space Usage Analysis

• buildDict: O(N), where N is the number of words in the dictionary. We store all words in the word_map hash map.
• search: O(1), as the search function uses a constant amount of extra space regardless of the input.

Edge Cases

1. Empty Dictionary: If the dictionary is empty, the search function should always return false.
2. Empty Search Word: If the search word is empty, the search function should return false.
3. Words of Different Lengths: Ensure that words of different lengths are not compared during the search, as they cannot possibly match with only one character difference.
4. Duplicate Words in Dictionary: The problem statement specifies that the words in the dictionary are distinct, so no specific handling is needed for duplicates.
5. Search Word is Identical to a Dictionary Word: If the search word is identical to a word in the dictionary, the search function should return false because it requires exactly one character difference.

These considerations ensure the MagicDictionary class behaves correctly under various scenarios.