Code Implementation

class MagicDictionary:

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

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

    def search(self, searchWord: str) -> bool:
        l = len(searchWord)
        if l not in self.words_by_length:
            return False
        for candidate in self.words_by_length[l]:
            diff = 0
            for a, b in zip(candidate, searchWord):
                if a != b:
                    diff += 1
                    if diff > 1:
                        break
            if diff == 1:
                return True
        return False
      

class MagicDictionary {
public:
    unordered_map<int, vector<string>> words_by_length;

    MagicDictionary() {}

    void buildDict(vector<string>& dictionary) {
        for (const string& word : dictionary) {
            words_by_length[word.size()].push_back(word);
        }
    }

    bool search(string searchWord) {
        int l = searchWord.size();
        if (words_by_length.find(l) == words_by_length.end()) return false;
        for (const string& candidate : words_by_length[l]) {
            int diff = 0;
            for (int i = 0; i < l; ++i) {
                if (candidate[i] != searchWord[i]) {
                    diff++;
                    if (diff > 1) break;
                }
            }
            if (diff == 1) return true;
        }
        return false;
    }
};
      

class MagicDictionary {
    private Map<Integer, List<String>> wordsByLength;

    public MagicDictionary() {
        wordsByLength = new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            int l = word.length();
            wordsByLength.computeIfAbsent(l, k -> new ArrayList<>()).add(word);
        }
    }

    public boolean search(String searchWord) {
        int l = searchWord.length();
        if (!wordsByLength.containsKey(l)) return false;
        for (String candidate : wordsByLength.get(l)) {
            int diff = 0;
            for (int i = 0; i < l; i++) {
                if (candidate.charAt(i) != searchWord.charAt(i)) {
                    diff++;
                    if (diff > 1) break;
                }
            }
            if (diff == 1) return true;
        }
        return false;
    }
}
      

var MagicDictionary = function() {
    this.wordsByLength = {};
};

MagicDictionary.prototype.buildDict = function(dictionary) {
    for (let word of dictionary) {
        let l = word.length;
        if (!(l in this.wordsByLength)) {
            this.wordsByLength[l] = [];
        }
        this.wordsByLength[l].push(word);
    }
};

MagicDictionary.prototype.search = function(searchWord) {
    let l = searchWord.length;
    if (!(l in this.wordsByLength)) return false;
    for (let candidate of this.wordsByLength[l]) {
        let diff = 0;
        for (let i = 0; i < l; i++) {
            if (candidate[i] !== searchWord[i]) {
                diff++;
                if (diff > 1) break;
            }
        }
        if (diff === 1) return true;
    }
    return false;
};
      

Problem Description

You are asked to design a data structure called MagicDictionary that supports two main operations:

• buildDict(dictionary): Build the dictionary from a list of unique words.
• search(searchWord): Return true if there is any word in the dictionary that differs from searchWord by exactly one character (i.e., you can change exactly one letter in searchWord to get a word from the dictionary). Otherwise, return false.

• All words are lowercase English letters.
• Words in the dictionary are unique.
• You must change exactly one character; no more, no less.
• Words must be the same length to be considered for a one-letter change.

Thought Process

At first glance, the problem seems to invite a brute-force approach: for each search, compare the searchWord to every word in the dictionary, count the number of differing characters, and return true if exactly one character differs. However, this is inefficient if the dictionary is large or if there are many queries.

To optimize, we notice a few key points:

• Only words of the same length can be considered, since changing a character can't change the word's length.
• We can group dictionary words by their lengths to quickly filter out impossible candidates.

Solution Approach

Here is a step-by-step breakdown of how to implement the Magic Dictionary efficiently:

1. Data Structure:
   • Use a hash map (dictionary) where the key is the word length, and the value is a list of words of that length. This allows O(1) access to all words of a given length.
2. Building the Dictionary:
   • For each word in the input dictionary, append it to the list associated with its length in the map.
3. Searching:
   • Given searchWord, look up the list of dictionary words with the same length.
   • For each candidate word in that list, compare it with searchWord character by character.
   • Count the number of positions where the characters differ.
   • If exactly one difference is found for any candidate, return true.
   • If none are found, return false.
4. Why this works:
   • Grouping by length drastically reduces the number of comparisons.
   • Comparing two words of length L takes O(L) time, and only a subset of words need to be checked for each query.

Example Walkthrough

Let's walk through an example:
Build Dictionary: ["hello", "hallo", "leetcode"]
Search: "hello"

• Words of length 5: ["hello", "hallo"]
• Compare "hello" vs "hello": 0 differences (not valid, must be exactly one)
• Compare "hello" vs "hallo": differences at position 1 ('e' vs 'a'), total 1 difference (valid!)
• Return true since one valid word exists.

• Words of length 5: ["hello", "hallo"]
• Compare "hhllo" vs "hello": differences at position 1 ('h' vs 'e'), total 1 difference (valid!)
• Return true

• No words of length 4 in dictionary. Return false.

• Words of length 8: ["leetcode"]
• Compare "leetcodd" vs "leetcode": differences at positions 6 ('d' vs 'e'), 7 ('d' vs 'e'), total 2 differences (not valid)
• Return false

Time and Space Complexity

Brute-force Approach:

• For each search, compare the searchWord to every word in the dictionary.
• If N is the number of words, and L is the average word length, time per search: O(N * L).

• Group words by length, so for a search, only words of the same length are checked.
• Let M be the number of words of the same length as searchWord. Time per search: O(M * L).
• Space: O(N * L) to store all words in the hash map.
• In practice, this is much faster, especially if the dictionary contains words of many different lengths.

Summary

The Magic Dictionary problem challenges us to efficiently find words that differ by exactly one character. By grouping dictionary words by their length, we reduce unnecessary comparisons and make each search operation much faster. The solution is elegant because it leverages simple data structures (hash maps and lists) to optimize both the build and search processes, making it practical for real-world use where many queries are expected.