LeetCode 676 - Implement Magic Dictionary

Difficulty: 🟡 Medium
Topics: Hash Table, String, Depth-First Search, Design, Trie

Solution

Problem Understanding

The problem asks us to design a dictionary-like data structure that supports two operations. First, we load a collection of distinct words into the structure. Second, given a query string, we determine whether it is possible to modify exactly one character in the query so that the resulting string matches one of the stored dictionary words.

The important detail is the phrase "exactly one character." This means:

We must change one character.
We cannot leave the word unchanged.
We cannot insert or delete characters.
The modified word must have the same length as the original query.

For example, if the dictionary contains "hello" and the query is "hhllo", we can change the second character from 'h' to 'e', producing "hello". Therefore the answer is true.

However, if the query is already "hello", the answer is false because zero modifications are needed, not exactly one.

The input consists of:

A dictionary array of unique lowercase English words.
Multiple search queries.

The output for each search query is a boolean indicating whether exactly one character replacement can transform the query into a dictionary word.

The constraints are relatively small:

At most 100 dictionary words.
Each word length is at most 100.
At most 100 search operations.

These limits are small enough that even moderately inefficient solutions can pass comfortably. This is important because it allows us to prioritize simplicity and clarity over highly optimized trie-based implementations.

Several edge cases are especially important:

The search word may already exist in the dictionary, but still must return false unless another dictionary word differs by exactly one character.
Words with different lengths can never match because only replacement operations are allowed.
Multiple dictionary words may share prefixes or differ by one character from each other.
Very short words such as length 1 require careful handling because replacing the only character is valid.

Approaches

Brute Force Approach

The most direct solution is to compare the search word against every word in the dictionary.

For each dictionary word:

If the lengths differ, skip it immediately because replacement operations cannot change length.
Otherwise, compare the two words character by character.
Count how many positions contain different characters.
If the number of differences is exactly one, return true.

If no dictionary word satisfies the condition, return false.

This approach is correct because it explicitly checks the exact requirement from the problem statement. Every candidate word is tested, and a match is accepted only when exactly one character differs.

Although this approach is technically brute force, the constraints are small enough that it is already efficient enough for LeetCode.

Optimized Observation

A more structured way to think about the problem is that only words of the same length are relevant. Therefore, instead of scanning every dictionary word blindly, we can group words by length.

This optimization avoids unnecessary comparisons against words that can never match.

The key insight is:

Replacement operations preserve word length.
Therefore, a query only needs to be compared against dictionary words of the same length.

We can store dictionary words in a hash map where the key is the word length and the value is the list of words with that length.

Then during search:

Retrieve only words with matching length.
Compare characters and count mismatches.
Return true if exactly one mismatch exists.

This reduces unnecessary work while keeping the implementation simple and readable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × L) per search	O(N × L)	Compare search word against every dictionary word
Optimal	O(K × L) per search	O(N × L)	Only compare against words with matching length

Here:

N is the number of dictionary words.
K is the number of dictionary words with the same length as the query.
L is the word length.

Algorithm Walkthrough

Optimal Algorithm

Initialize a hash map that groups words by their length.

The reason for grouping by length is that only words with the same length can possibly match after exactly one replacement. This immediately removes impossible candidates. 2. During buildDict, iterate through each dictionary word.

For every word:

Compute its length.
Insert the word into the list associated with that length.

This preprocessing step organizes the dictionary efficiently for future searches. 3. During search, first determine the length of the query word.

If there are no dictionary words of that length, immediately return false because replacement operations cannot change string length. 4. Iterate through all dictionary words with matching length.

For each candidate word:

Initialize a mismatch counter to zero.
Compare characters at every index.

While comparing characters:

If the characters differ, increment the mismatch counter.
If the mismatch counter exceeds one, stop checking this word early because it already violates the requirement.

Early termination improves efficiency and avoids unnecessary comparisons. 6. After comparing the full word:

If the mismatch count is exactly one, return true.
Otherwise continue checking other candidate words.

If no candidate produces exactly one mismatch, return false.

Why it works

The algorithm is correct because it checks every dictionary word that could possibly match the search word. Words with different lengths are impossible candidates and are safely ignored. For every valid-length candidate, the algorithm counts differing character positions exactly. A word is accepted only when the mismatch count equals one, which precisely matches the problem requirement.

Python Solution

from collections import defaultdict
from typing import List

class MagicDictionary:

    def __init__(self):
        self.words_by_length = defaultdict(list)

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

    def search(self, searchWord: str) -> bool:
        target_length = len(searchWord)

        if target_length not in self.words_by_length:
            return False

        for candidate in self.words_by_length[target_length]:
            differences = 0

            for index in range(target_length):
                if searchWord[index] != candidate[index]:
                    differences += 1

                    if differences > 1:
                        break

            if differences == 1:
                return True

        return False

# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)

The implementation begins by creating a defaultdict(list) named words_by_length. This groups dictionary words according to their lengths, allowing the search operation to ignore impossible candidates immediately.

The buildDict method iterates through every dictionary word and appends it to the list corresponding to its length.

The search method first computes the query length. If no words of that length exist, it immediately returns False.

Next, the method iterates through every candidate word with the same length. For each candidate, it counts character mismatches. If more than one mismatch occurs, the loop stops early because the candidate can no longer satisfy the requirement.

If exactly one mismatch exists after comparing all characters, the method returns True. Otherwise, after all candidates are checked, the method returns False.

Go Solution

package main

type MagicDictionary struct {
	wordsByLength map[int][]string
}

func Constructor() MagicDictionary {
	return MagicDictionary{
		wordsByLength: make(map[int][]string),
	}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	for _, word := range dictionary {
		length := len(word)
		this.wordsByLength[length] = append(this.wordsByLength[length], word)
	}
}

func (this *MagicDictionary) Search(searchWord string) bool {
	targetLength := len(searchWord)

	candidates, exists := this.wordsByLength[targetLength]
	if !exists {
		return false
	}

	for _, candidate := range candidates {
		differences := 0

		for i := 0; i < targetLength; i++ {
			if searchWord[i] != candidate[i] {
				differences++

				if differences > 1 {
					break
				}
			}
		}

		if differences == 1 {
			return true
		}
	}

	return false
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.BuildDict(dictionary);
 * param_2 := obj.Search(searchWord);
 */

The Go implementation closely mirrors the Python solution. The primary difference is that Go uses a map[int][]string instead of Python's defaultdict.

Go strings are byte-indexable, which works correctly here because the problem guarantees lowercase English letters only. No Unicode handling is required.

The map lookup returns both the candidate slice and a boolean indicating whether the key exists. This avoids unnecessary iteration when no words of the required length are present.

Worked Examples

Example 1

Dictionary:

["hello", "leetcode"]

After buildDict:

Length	Words
5	["hello"]
8	["leetcode"]

Search `"hello"`

Candidate words of length 5:

Candidate	Differences
hello	0

Since exactly one difference is required, return false.

Search `"hhllo"`

Candidate words of length 5:

Index	Search Word	Candidate	Different?
0	h	h	No
1	h	e	Yes
2	l	l	No
3	l	l	No
4	o	o	No

Total differences = 1

Return true.

Search `"hell"`

There are no dictionary words of length 4.

Return false.

Search `"leetcoded"`

There are no dictionary words of length 9.

Return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(K × L) per search	Compare against same-length words only
Space	O(N × L)	Store all dictionary words

Here:

N is the number of dictionary words.
L is the maximum word length.
K is the number of words sharing the same length as the search word.

The preprocessing step stores all words grouped by length, requiring linear space proportional to the total dictionary size.

During search, each candidate word of matching length is scanned character by character. Since mismatches terminate early once the count exceeds one, practical performance is often better than the worst case.

Test Cases

from typing import List
from collections import defaultdict

class MagicDictionary:

    def __init__(self):
        self.words_by_length = defaultdict(list)

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

    def search(self, searchWord: str) -> bool:
        target_length = len(searchWord)

        if target_length not in self.words_by_length:
            return False

        for candidate in self.words_by_length[target_length]:
            differences = 0

            for i in range(target_length):
                if searchWord[i] != candidate[i]:
                    differences += 1

                    if differences > 1:
                        break

            if differences == 1:
                return True

        return False

magic = MagicDictionary()
magic.buildDict(["hello", "leetcode"])

assert magic.search("hello") == False  # exact match, needs 0 changes
assert magic.search("hhllo") == True   # exactly one replacement works
assert magic.search("hell") == False   # different length
assert magic.search("leetcoded") == False  # different length

magic2 = MagicDictionary()
magic2.buildDict(["a"])

assert magic2.search("b") == True   # one character replacement
assert magic2.search("a") == False  # zero replacements not allowed

magic3 = MagicDictionary()
magic3.buildDict(["abc"])

assert magic3.search("abd") == True   # one differing character
assert magic3.search("acc") == True   # one differing character
assert magic3.search("abc") == False  # exact match only
assert magic3.search("xyz") == False  # more than one difference

magic4 = MagicDictionary()
magic4.buildDict(["abcd", "abcf", "zzzz"])

assert magic4.search("abce") == True  # matches multiple candidates
assert magic4.search("zzza") == True  # one difference at end
assert magic4.search("aaaa") == False # multiple differences

magic5 = MagicDictionary()
magic5.buildDict(["aa", "bb"])

assert magic5.search("ab") == True   # matches both with one change
assert magic5.search("cc") == False  # differs by two chars from both

Test	Why
`"hello"`	Verifies exact matches are rejected
`"hhllo"`	Verifies one replacement succeeds
`"hell"`	Verifies different lengths fail
`"a"` vs `"b"`	Tests single-character words
`"xyz"`	Tests multiple mismatches
`"abce"`	Tests multiple valid candidates
`"aaaa"`	Tests rejection when differences exceed one
`"cc"`	Tests no valid transformation exists

Edge Cases

Exact Match Exists in the Dictionary

One subtle case occurs when the search word already exists in the dictionary. A naive implementation might incorrectly return true because the word is found.

However, the problem requires exactly one character modification. Zero modifications are not allowed.

For example:

Dictionary: ["hello"]
Search: "hello"

The implementation correctly counts zero differences and rejects the match because the mismatch count must equal exactly one.

Different Word Lengths

Another important edge case involves strings of different lengths.

Since only character replacement is allowed, insertion and deletion operations are invalid. Therefore, words with different lengths can never match.

For example:

Dictionary: ["hello"]
Search: "hell"

The implementation handles this efficiently by grouping words by length and immediately returning false if no same-length candidates exist.

Multiple Differences

A candidate word may differ in more than one position.

For example:

Dictionary: ["hello"]
Search: "world"

There are multiple mismatched positions, so the answer must be false.

The implementation tracks mismatches during comparison and exits early once the count exceeds one. This both improves efficiency and guarantees correctness.

LeetCode 676 - Implement Magic Dictionary

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimized Observation

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Search "hello"

Search "hhllo"

Search "hell"

Search "leetcoded"

Complexity Analysis

Test Cases

Edge Cases

Exact Match Exists in the Dictionary

Different Word Lengths

Multiple Differences

Search `"hello"`

Search `"hhllo"`

Search `"hell"`

Search `"leetcoded"`