Implement Magic Dictionary: One-Character Fuzzy Matching

You need to design a data structure called MagicDictionary that supports two operations. buildDict takes a list of words and stores them. search takes a word and returns true if you can change exactly one character in the word to match some word in the dictionary. Not zero characters, not two. Exactly one.

This is LeetCode 676: Implement Magic Dictionary, and the key insight is that "exactly one character different" is a very specific constraint you can check efficiently by grouping words by length first.

The approach: group by length, compare character by character

The simplest and most effective approach avoids building a trie entirely. Instead, you group the dictionary words by their length in a hash map. When a search query comes in, you only need to compare it against words of the same length, since words of different lengths can never differ by exactly one character.

For each candidate word of matching length, you compare characters one by one and count how many positions differ. If exactly one position differs, you have a match and return true. If zero positions differ, the word is identical to the query, which does not count. If two or more positions differ, that candidate cannot work.

This is efficient because most queries will only need to check a small subset of the dictionary. Words of a different length are filtered out immediately, and the character comparison short-circuits as soon as the difference count exceeds one.

The solution

class MagicDictionary:
    def __init__(self):
        self.groups = {}

    def buildDict(self, dictionary):
        self.groups = {}
        for word in dictionary:
            length = len(word)
            if length not in self.groups:
                self.groups[length] = []
            self.groups[length].append(word)

    def search(self, searchWord):
        length = len(searchWord)
        if length not in self.groups:
            return False
        for word in self.groups[length]:
            diffs = 0
            for a, b in zip(searchWord, word):
                if a != b:
                    diffs += 1
                if diffs > 1:
                    break
            if diffs == 1:
                return True
        return False

Walking through an example

Suppose the dictionary contains ["hello", "hallo", "leet"] and we search for "hhllo". First, buildDict groups the words: length 5 gets ["hello", "hallo"] and length 4 gets ["leet"].

When we call search("hhllo"), the search word has length 5, so we only look at the length-5 bucket. We compare "hhllo" with "hello" character by character: h=h, h!=e, l=l, l=l, o=o. That gives us exactly 1 difference, so we return True immediately without even checking "hallo".

If we had searched for "hello" instead, comparing with "hello" gives 0 differences (identical, skip), and comparing with "hallo" gives 1 difference at index 1 (e vs a), so that would also return True.

Complexity

Here n is the number of words in the dictionary with the same length as the search word, and k is the length of the search word. Building the dictionary takes O(total characters) time. Each search filters by length first, then does an O(k) comparison for each candidate. In the worst case every word has the same length, but in practice the length filter eliminates most words quickly. Space is O(total characters) to store all dictionary words.

Edge cases

• Search word matches a dictionary word exactly: zero differences means it does not count. You must change exactly one character, not zero.
• Dictionary contains duplicate words: if the dictionary has ["hello", "hello"] and you search for "hello", comparing with the first copy gives 0 diffs and comparing with the second copy also gives 0 diffs. The answer is False because no single-character change was made.
• Single character words: buildDict(["a"]) and search("b") returns True (one diff). search("a") returns False (zero diffs).
• No words of matching length: if the search word has length 3 but no dictionary words have length 3, return False immediately without any comparisons.

The building blocks

Hash map grouping

Grouping items by a key property (here, word length) is a fundamental technique for reducing the search space. Instead of comparing a query against every item, you only compare against items that could possibly match. This same pattern appears in group anagrams (grouping by sorted characters) and bucket sort (grouping by value range).

Character-by-character comparison with early exit

Comparing two strings position by position and counting differences is the core operation. The early exit when diffs > 1 is important for performance. Without it, you would always scan the full length of every candidate. With it, you bail out as soon as a second mismatch appears, which in practice makes most comparisons very fast.

Exactly-one constraint

The "exactly one difference" constraint is more subtle than "at most one." You must reject identical matches (zero differences), which means you cannot simply check for a loose similarity threshold. This pattern, where the constraint is an exact count rather than a bound, appears in problems like edit distance queries and Hamming distance checks.

From understanding to recall

The core pattern here is grouping by a filtering property (length) and then doing a targeted comparison (character diff count). The implementation is short and there is really only one non-obvious detail to remember: zero differences means the word is identical, which does not satisfy the "change exactly one character" requirement. That single edge case is what separates a correct solution from a buggy one.

When you practice this problem with spaced repetition, focus on two things. First, the grouping step and why it helps. Second, the exact comparison logic, especially the distinction between diffs == 0, diffs == 1, and diffs > 1. Once those two pieces are automatic, you can write the full solution in under five minutes.

Related posts

• Design Add and Search Words - A closely related problem using a trie with wildcard dot matching instead of one-character change
• Implement Trie - The foundational trie data structure that provides an alternative approach to this problem
• Longest Common Subsequence - Another string comparison problem where character-by-character analysis drives the solution