LeetCode 676: Implement Magic Dictionary

Problem Restatement

We need to design a data structure called MagicDictionary.

It supports two operations:

The important rule is exactly one character must be changed. Zero changes do not count. Two or more changes do not count. The modified word must exist in the dictionary.

For example, if the dictionary contains:

["hello", "leetcode"]

Then:

search("hello")    # false
search("hhllo")    # true
search("hell")     # false
search("leetcoded") # false

"hello" returns false because it matches a dictionary word with zero changes.

"hhllo" returns true because changing the second character from 'h' to 'e' gives "hello".

Input and Output

The dictionary words are distinct.

The search operation only allows character replacement. It cannot insert or delete characters. Therefore, only words with the same length as searchWord can match.

Examples

Example:

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

magicDictionary.search("hello")      # false
magicDictionary.search("hhllo")      # true
magicDictionary.search("hell")       # false
magicDictionary.search("leetcoded")  # false

Explanation:

First Thought: Compare Against Every Word

A direct solution is to store all dictionary words in a list.

When search(searchWord) is called, compare searchWord with every dictionary word of the same length.

For each candidate word, count how many positions differ.

If the number of differences is exactly 1, return true.

Otherwise, keep checking.

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

            for a, b in zip(word, searchWord):
                if a != b:
                    diff += 1

            if diff == 1:
                return True

        return False

This is easy to understand and valid.

Problem With the Direct Solution

The direct solution may compare the query against many words.

If there are n words and each word has length m, then one search can take:

O(n * m)

This may be acceptable for small input, but the data structure can be improved by precomputing patterns.

Key Insight

Two words differ by exactly one character if they have the same length and become the same pattern after replacing one position with a wildcard.

For example:

hello

Its wildcard patterns are:

*ello
h*llo
he*lo
hel*o
hell*

Now consider:

hhllo

Its wildcard patterns are:

*hllo
h*llo
hh*lo
hhl*o
hhll*

Both "hello" and "hhllo" share this pattern:

h*llo

That means they are the same except at the wildcard position.

So we can build a map from wildcard patterns to the original character that appeared at the wildcard position.

Algorithm

During buildDict:

For every word in the dictionary:

1. Replace each character position with '*'.
2. Use the resulting pattern as a key.
3. Store the character that was replaced.

For example, for "hello":

If the same pattern appears with different replaced characters, then any word with that pattern can match by changing one character.

To represent that, we can store a special marker such as '*'.

During search:

1. Generate every wildcard pattern of searchWord.
2. Look up the pattern.
3. If the stored character is different from the current character, return true.
4. Otherwise, continue.
5. Return false if no pattern works.

The condition “stored character is different from the current character” enforces exactly one changed character.

Correctness

For any returned true, the algorithm found a wildcard pattern from searchWord that also exists in the built dictionary.

That means there is a dictionary word with the same length and the same characters at every position except the wildcard position.

The algorithm also checks that the replaced character differs from the search word’s character. Therefore, the dictionary word differs from searchWord by exactly one character.

For any valid match, suppose some dictionary word differs from searchWord by exactly one character at index i.

If we replace index i in both words with '*', both words produce the same wildcard pattern.

This pattern was inserted during buildDict.

When search generates the same pattern, it finds the stored entry and sees that the character at index i is different. Therefore, the algorithm returns true.

So the algorithm returns true exactly when one character can be changed to form a dictionary word.

Complexity

Let:

For each word, we create one pattern per character. Creating a pattern by slicing costs O(m).

The space can be described as the number of stored patterns times the pattern length.

Implementation

class MagicDictionary:

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

    def buildDict(self, dictionary: list[str]) -> None:
        for word in dictionary:
            for i, ch in enumerate(word):
                pattern = word[:i] + "*" + word[i + 1:]

                if pattern in self.patterns:
                    self.patterns[pattern] = "*"
                else:
                    self.patterns[pattern] = ch

    def search(self, searchWord: str) -> bool:
        for i, ch in enumerate(searchWord):
            pattern = searchWord[:i] + "*" + searchWord[i + 1:]

            if self.patterns.get(pattern, ch) != ch:
                return True

        return False

Code Explanation

The dictionary:

self.patterns = {}

maps wildcard patterns to the character that was removed from the dictionary word.

For example:

"hello" -> "h*llo"

stores:

self.patterns["h*llo"] = "e"

If another dictionary word creates the same pattern, we set the value to "*":

if pattern in self.patterns:
    self.patterns[pattern] = "*"

This means the pattern can be formed from multiple words, possibly with different characters at the replaced position.

In search, we generate the same kind of wildcard pattern:

pattern = searchWord[:i] + "*" + searchWord[i + 1:]

Then we check:

if self.patterns.get(pattern, ch) != ch:
    return True

This line has two cases.

If the pattern does not exist, get(pattern, ch) returns ch, so the condition is false.

If the pattern exists with the same character, that means the word may be identical at this position, so it does not prove exactly one change.

If the pattern exists with a different character, then replacing the current character can produce a dictionary word.

The marker "*" is also different from any lowercase letter, so it correctly returns true when multiple dictionary words share the same pattern.

Testing

def run_tests():
    obj = MagicDictionary()
    obj.buildDict(["hello", "leetcode"])

    assert obj.search("hello") is False
    assert obj.search("hhllo") is True
    assert obj.search("hell") is False
    assert obj.search("leetcoded") is False

    obj = MagicDictionary()
    obj.buildDict(["hello", "hallo"])

    assert obj.search("hello") is True
    assert obj.search("hhllo") is True
    assert obj.search("hella") is True

    obj = MagicDictionary()
    obj.buildDict(["a", "b"])

    assert obj.search("a") is True
    assert obj.search("c") is True
    assert obj.search("aa") is False

    print("all tests passed")

run_tests()

Test meaning: