LeetCode 676: Implement Magic Dictionary Solution in Python – A Step-by-Step Guide

What Is LeetCode 676: Implement Magic Dictionary?

In LeetCode 676: Implement Magic Dictionary, you need to implement a MagicDictionary class with two main methods:

• buildDict(words): Builds the dictionary from a list of words.
• search(word): Returns True if the given word can be formed by changing exactly one character in any dictionary word, False otherwise.

For example, if the dictionary contains ["hello", "leet"], then search("hhllo") returns True (matches "hello" with one change: h→e), but search("hell") returns False (no match with one change). The problem tests your ability to design a data structure for efficient string matching with a single modification.

Problem Statement

• Class: MagicDictionary
• Methods:
• buildDict(words: List[str]) -> None: Initialize with word list.
• search(word: str) -> bool: Check if word matches with one change.
• Rules:
• Change exactly one character in a dictionary word.
• Return True if match exists, False otherwise.
• Words are lowercase English letters.

Constraints

• 1 ≤ words.length ≤ 100.
• 1 ≤ words[i].length ≤ 100.
• words[i] consists of lowercase English letters.
• All words in words are unique.
• At most 100 calls to search.

Examples

• Input:
• ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
• [[], [["hello", "leet"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
• Output: [null, null, False, True, False, False]
• buildDict(["hello", "leet"]): Initializes dictionary.
• search("hello"): False (no change needed).
• search("hhllo"): True (h→e matches "hello").
• search("hell"): False (no match with one change).
• search("leetcoded"): False (no match with one change).

These examples set the dictionary—let’s solve it!

Understanding the Problem: Building a Magic Dictionary

To solve LeetCode 676: Implement Magic Dictionary in Python, we need to create a MagicDictionary class that efficiently stores words and checks if a search word can match a stored word by changing exactly one character. A brute-force approach—checking each dictionary word with all possible single-character changes—would be O(n * l * 26) per search (n = words, l = length), reasonable for small constraints but slow for frequent calls. Since we’re dealing with string prefixes and modifications, a trie or simple iteration can optimize this. We’ll use:

• Best Solution (Trie with Search Modification): O(l) build, O(l) search time, O(n * l) space—fast and scalable.
• Alternative Solution (Brute-Force with Character Replacement): O(n l) build, O(n l 26) search time, O(n l) space—simple but slow.

Let’s start with the trie solution, breaking it down for beginners.

Best Solution: Trie with Search Modification

Why This Is the Best Solution

The trie with search modification approach is the top choice for LeetCode 676 because it’s efficient—O(l) time per search with O(n * l) space—and uses a trie (prefix tree) to store words, allowing a clever DFS search that tries one character change at each position while leveraging prefix matching. It fits constraints (n, l ≤ 100) perfectly and is intuitive once you see the trie structure. It’s like building a word tree and magically tweaking one branch to find a match!

How It Works

Think of this as a word weaver:

• Step 1: Build Trie:
• Create a trie node with children (dict) and is_end flag.
• For each word, insert into trie, marking end.
• Step 2: Search with Modification:
• DFS through trie with search word:
• Track position and changes used (0 or 1).
• At each char:
• Match: Follow child, no change.
• Mismatch: Try each possible char (a-z), use change if unused.
• Return True if reach end with exactly one change.
• Step 3: Return Result:
• Return search outcome.

It’s like a trie matcher—build and tweak!

Step-by-Step Example

Example: buildDict(["hello", "leet"]), search("hhllo")

• Step 1: Build Trie:
• "hello": h→e→l→l→o (is_end=True).
• "leet": l→e→e→t (is_end=True).
• Trie root: {h: {e:...}, l: {e:...}}.
• Step 2: Search "hhllo":
• Start: root, pos=0, changes=0.
• h matches h, pos=1, changes=0.
• h vs e, mismatch:
• Try e (child exists), pos=2, changes=1.
• l matches l, pos=3, changes=1.
• l matches l, pos=4, changes=1.
• o matches o, pos=5, changes=1, is_end=True, return True.
• Other paths (e.g., changes=0) fail or exceed changes.
• Step 3: Return True.
• Output: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass TrieNode:
    def __init__(self):
        self.children = {}  # Dict of char to TrieNode
        self.is_end = False  # Marks end of word

class MagicDictionary:
    def __init__(self):
        self.root = TrieNode()

    def buildDict(self, dictionary: List[str]) -> None:
        # Step 1: Build trie from dictionary
        for word in dictionary:
            node = self.root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_end = True

    def search(self, searchWord: str) -> bool:
        # Step 2: DFS search with one modification
        def dfs(node, pos, changes, word):
            if pos == len(word):
                return changes == 1 and node.is_end
            if changes > 1:
                return False

            char = word[pos]
            # Try matching current char
            if char in node.children:
                if dfs(node.children[char], pos + 1, changes, word):
                    return True

            # Try changing current char
            if changes == 0:
                for c in node.children:
                    if c != char:
                        if dfs(node.children[c], pos + 1, 1, word):
                            return True
            return False

        return dfs(self.root, 0, 0, searchWord)

• Lines 1-5: TrieNode: Children dict, end flag.
• Lines 8-10: __init__: Root node.
• Lines 12-20: buildDict:
• Insert each word into trie, mark end.
• Lines 23-41: search:
• DFS: Track pos and changes, match or modify one char, check end condition.
• Time Complexity: Build O(n * l), Search O(l)—l = word length.
• Space Complexity: O(n * l)—trie size.

This is like a word magician—build and match!

Alternative Solution: Brute-Force with Character Replacement

Why an Alternative Approach?

The brute-force with character replacement approach stores words directly—O(n * l) build time, O(n * l * 26) search time, O(n * l) space. It’s simpler, checking each dictionary word by trying all single-character replacements, but inefficient for frequent searches. It’s like manually testing every spell variation!

How It Works

Picture this as a word tester:

• Step 1: Store words in list.
• Step 2: Search by replacement:
• For each dictionary word:
• If same length as search word:
• Try replacing each char with a-z.
• Check if matches search word with one change.
• Step 3: Return result.

It’s like a spell checker—store and test!

Step-by-Step Example

Example: Same as above

sembrado- Step 1: Words = ["hello", "leet"].

• Step 2: Search "hhllo":
• "hello":
• Pos 0: ehllo, hhllo (match, 1 change), return True.
• No need to check "leet" (length mismatch).
• Step 3: Return True.
• Output: True.

Code for Brute-Force Approach

Copy codeclass 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 i in range(len(word)):
                if word[i] != searchWord[i]:
                    diff += 1
                if diff > 1:
                    break
            if diff == 1:
                return True
        return False

• Lines 4-5: __init__: Empty word list.
• Lines 7-8: buildDict: Store words.
• Lines 10-22: search:
• Compare each word, count differences, return True if exactly one.
• Time Complexity: Build O(n l), Search O(n l * 26)—n words, l length.
• Space Complexity: O(n * l)—word storage.

It’s a word comparer—check and match!

Comparing the Two Solutions

• Trie (Best):
• Pros: O(l) search, O(n * l) space, efficient for searches.
• Cons: Trie structure less obvious.
• Brute-Force (Alternative):
• Pros: O(n l 26) search, O(n * l) space, simple.
• Cons: Slower for multiple searches.

Trie wins for efficiency.

Additional Examples and Edge Cases

• Input: ["hello"], "hello"
• Output: False.
• Input: ["hello"], "heelo"
• Output: True.

Trie handles these well.

Complexity Breakdown

• Trie: Build O(n l), Search O(l), Space O(n l).
• Brute-Force: Build O(n l), Search O(n l 26), Space O(n l).

Trie is optimal for search.

Key Takeaways

• Trie: Prefix magic—smart!
• Brute-Force: Character testing—clear!
• Dictionary: Matching is fun.
• Python Tip: Tries rock—see Python Basics.

Final Thoughts: Cast That Spell

LeetCode 676: Implement Magic Dictionary in Python is a fun dictionary challenge. Trie with search modification offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 208: Implement Trie or LeetCode 211: Design Add and Search Words Data Structure. Ready to weave? Head to Solve LeetCode 676 on LeetCode and build that magic dictionary today!