LeetCode Solutions Blog

Implement Magic Dictionary

Number: 676

Difficulty: Medium

Paid? No

Problem Description

Design a data structure that is initialized with a list of unique words. It supports a search query where, given a word, you determine if you can modify exactly one character to match any word in the dictionary.

Key Insights

Only words with the same length as the search word can be candidates.
For each candidate word, compare characters at each position; there must be exactly one difference.
Using a hash table grouped by word lengths can lead to efficient comparisons.
Alternative methods include using a Trie with support for "wildcard" matching, but grouping by word length is simpler given the constraints.

Space and Time Complexity

Time Complexity: O(N * L) per search, where N is the number of words with the matching length and L is the word length. Space Complexity: O(Total characters in dictionary), which is the space needed to store all the words.

Solution

We design the MagicDictionary class with two main methods: buildDict and search. In buildDict, we store all words in a hash table keyed by their length. This allows us to quickly filter candidates during the search. During search, we only iterate over the words that have the same length as the search word and count the differences at each character. If exactly one difference is found, we return true; otherwise, false. This approach avoids unnecessary comparisons and works well within the given constraints.

Code Solutions

class MagicDictionary:
    def __init__(self):
        # Initialize a dictionary where key is word length and value is list of words.
        self.words_by_length = {}

    def buildDict(self, dictionary):
        # Populate the dictionary grouping words by their length.
        for word in dictionary:
            self.words_by_length.setdefault(len(word), []).append(word)

    def search(self, searchWord):
        # If there is no group of words matching the length of searchWord, return False.
        candidates = self.words_by_length.get(len(searchWord), [])
        for word in candidates:
            differences = 0
            # Compare each character in searchWord and candidate word.
            for c1, c2 in zip(searchWord, word):
                if c1 != c2:
                    differences += 1
                    # If more than one difference, break early.
                    if differences > 1:
                        break
            # Return True if exactly one difference was found.
            if differences == 1:
                return True
        return False

# Example usage:
# magicDictionary = MagicDictionary()
# magicDictionary.buildDict(["hello", "leetcode"])
# print(magicDictionary.search("hello"))  # False
# print(magicDictionary.search("hhllo"))  # True
# print(magicDictionary.search("hell"))   # False
# print(magicDictionary.search("leetcoded"))  # False