Problem Description

You need to design a data structure called MagicDictionary that can determine if a given string can be transformed into any word in a pre-loaded dictionary by changing exactly one character.

The data structure should support the following operations:

1. MagicDictionary(): Initializes an empty MagicDictionary object.

2. buildDict(dictionary): Takes an array of distinct strings and stores them in the data structure. This sets up your dictionary of valid words.

3. search(searchWord): Takes a string and returns true if you can change exactly one character in searchWord to match any word stored in the dictionary. Returns false otherwise.

Important constraints:

• You must change exactly one character - no more, no less
• The change must result in a word that exists in the dictionary
• All words in the dictionary are distinct

For example, if your dictionary contains ["hello", "hallo"] and you search for "hello", the result would be true because you can change the 'e' to 'a' to get "hallo" which is in the dictionary. However, if you search for "hallo", it would also return true because you can change the 'a' to 'e' to get "hello".

The solution uses a Trie data structure combined with depth-first search (DFS) to efficiently check all possible single-character modifications. During the search, it tracks whether exactly one character has been changed and validates that the resulting word exists in the dictionary.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The Trie data structure used in this problem is essentially a tree (which is a special type of graph). Each node represents a character, and edges connect characters to form words. The dictionary words are stored as paths from root to leaf nodes.

Is it a tree?

• Yes: A Trie is specifically a tree data structure. It has a single root node, and each node can have multiple children (one for each possible character), with no cycles.

DFS

• Yes: Since we're working with a tree structure and need to explore paths from root to leaf while tracking modifications, DFS is the appropriate choice.

Conclusion: The flowchart leads us directly to using DFS for this problem.

Why DFS is Perfect for This Problem

The DFS approach works particularly well here because:

1. Path Exploration: We need to traverse from the root of the Trie to a leaf node, checking each character along the way. DFS naturally follows paths from start to end.

2. Backtracking Capability: When we encounter a mismatch, we need to either:

   • Use our one allowed modification and continue down that path
   • Try different branches (different character substitutions)

   DFS with backtracking handles this elegantly.

3. State Tracking: During traversal, we need to track whether we've used our one allowed character change. The recursive nature of DFS makes it easy to pass this state (diff parameter) through the traversal.

4. Early Termination: DFS allows us to stop exploring a path as soon as we know it won't lead to a valid solution (e.g., when we've already used our one modification and encounter another mismatch).

The search process explores the Trie depth-first, maintaining the count of character differences, and returns true only when exactly one character has been modified and we've reached a valid word ending.

Intuition

When we need to check if we can transform a word by changing exactly one character, the naive approach would be to generate all possible single-character modifications and check if any exist in our dictionary. However, this would be inefficient, especially with repeated searches.

The key insight is that we can leverage the structure of a Trie to guide our search more intelligently. Instead of generating all modifications upfront, we can explore the Trie path-by-path and make decisions at each character position.

Think of it like walking through a maze where you have one "magic pass" that lets you walk through exactly one wall. As you traverse each path in the Trie:

1. When characters match: Continue following the current path without using your magic pass
2. When characters don't match: You have two choices:
   • If you haven't used your magic pass yet, use it now to pretend this character matches and continue
   • Try other branches at this position (effectively trying different character substitutions)

The beauty of this approach is that we're not blindly trying all possible modifications. Instead, we're letting the Trie structure guide us to only explore modifications that could potentially lead to valid words in our dictionary.

The recursive DFS naturally handles the backtracking needed when a path doesn't work out. If we reach the end of a word in the Trie and we've used our magic pass exactly once, we've found a valid match. If we've used it zero times (perfect match) or more than once (too many differences), it's not what we're looking for.

This approach elegantly combines the efficiency of Trie lookups with the flexibility of DFS exploration, allowing us to check all possible single-character modifications without explicitly generating them.

Learn more about Depth-First Search and Trie patterns.

Solution Approach

The solution uses a Trie data structure combined with DFS to efficiently handle the search for words with exactly one character difference. Let's walk through the implementation:

Building the Trie Structure

The [Trie](/problems/trie_intro) class has two main components:

• children: A dictionary mapping characters to child Trie nodes
• is_end: A boolean flag marking the end of a valid word

The insert method adds words to the Trie by creating a path from root to leaf, with each node representing a character. When we reach the end of a word, we mark is_end = True.

The DFS Search Strategy

The core logic lies in the search method, which uses a nested DFS function with three parameters:

• i: Current position in the search word
• node: Current node in the Trie
• diff: Number of character differences encountered so far (0 or 1)

The DFS explores two scenarios at each character position:

1. Exact Match Path: If w[i] exists in node.children, we can follow this path without using our modification:

   if w[i] in node.children and dfs(i + 1, node.children[w[i]], diff):
       return True

2. Modification Path: If we haven't used our modification yet (diff == 0), we can try changing the current character to any other available character in the Trie:

   return diff == 0 and any(
       dfs(i + 1, node.children[c], 1) for c in node.children if c != w[i]
   )

   This tries all possible character substitutions at the current position, marking diff = 1 to indicate we've used our one allowed change.

Base Case and Validation

When we reach the end of the search word (i == len(w)), we check two conditions:

• diff == 1: We must have changed exactly one character
• node.is_end: We must be at a valid word ending in the Trie

Both conditions must be true for a successful match.

MagicDictionary Wrapper

The MagicDictionary class simply wraps the Trie functionality:

• buildDict: Inserts all dictionary words into the Trie
• search: Delegates to the Trie's search method

This approach has a time complexity of O(n * m) for building the dictionary (where n is the number of words and m is the average word length) and O(m * 26) for searching (where we might explore up to 26 different character branches at each position).

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Setup: Build a dictionary with words ["hello", "hallo", "leetc"]

The Trie structure after building looks like this:

        root
       /    \
      h      l
      |      |
      e,a    e
      |      |
      l      e
      |      |
      l      t
      |      |
      o*     c*

(* marks end of word)

Search 1: Search for "hello" (should return true)

Starting DFS with i=0, node=root, diff=0:

1. At position 0 ('h'):

   • Found 'h' in children, follow exact match path
   • Continue with i=1, node=h_node, diff=0

2. At position 1 ('e'):

   • Found 'e' in children, follow exact match path
   • Continue with i=2, node=e_node, diff=0

3. At position 2 ('l'):

   • Found 'l' in children, follow exact match path
   • Continue with i=3, node=l_node, diff=0

4. At position 3 ('l'):

   • Found 'l' in children, follow exact match path
   • Continue with i=4, node=l_node, diff=0

5. At position 4 ('o'):

   • Found 'o' in children, follow exact match path
   • Continue with i=5, node=o_node, diff=0

6. Reached end (i=5):

   • Check: diff == 1? No (diff=0) → return false
   • Backtrack to position 1

7. Back at position 1 ('e'), try modification path:

   • Since diff=0, we can try changing 'e' to 'a'
   • Continue with i=2, node=a_node, diff=1

8. Continue down the 'a' branch with remaining "llo":

   • All characters match in the Trie
   • Reach end with diff=1 and is_end=True
   • Return true!

Search 2: Search for "leetd" (should return true)

Starting DFS with i=0, node=root, diff=0:

1. Follow exact matches for "leet" (positions 0-3)
2. At position 4 ('d'):
   • 'd' not in children at this node
   • Since diff=0, try modification to 'c' (available in Trie)
   • Continue with i=5, node=c_node, diff=1
3. Reached end with diff=1 and is_end=True → return true

Search 3: Search for "hxllo" (should return false)

1. At position 0 ('h'): Follow 'h' path
2. At position 1 ('x'):
   • 'x' not in children
   • Try modifications to 'e' or 'a' with diff=1
3. Following 'e' path with "llo" → reaches valid word
4. But we changed 'x'→'e', making "hello" which exists!
5. Return true

Wait, let me reconsider Search 3...

Search 3 (corrected): Search for "world" (should return false)

1. At position 0 ('w'):
   • 'w' not in children of root
   • Since diff=0, try modifications to 'h' or 'l'
2. If we change to 'h', we'd need "orld" to match remaining path
   • But Trie only has "ello" or "allo" after 'h'
   • No match possible
3. If we change to 'l', we'd need "orld" to match remaining path
   • But Trie only has "eetc" after 'l'
   • No match possible
4. All paths exhausted → return false

This example demonstrates how the DFS explores both exact match paths and modification paths, backtracking when needed, and only returns true when exactly one character difference leads to a valid dictionary word.

Solution Implementation

Time and Space Complexity

Time Complexity:

• buildDict: Building the trie requires iterating through each word in the dictionary and inserting each character. For n words with average length l, this takes O(n × l) time.
• search: For each search operation, we perform a DFS traversal. In the worst case:
  • We traverse through all l characters of the search word
  • At each position, when diff = 0 (no difference used yet), we potentially explore all children except the matching character
  • This means checking up to |Σ| - 1 alternative branches (where |Σ| = 26 for lowercase letters)
  • Each branch continues the DFS for the remaining characters
  • This gives us O(l × |Σ|) time per search operation

Overall time complexity: O(n × l + q × l × |Σ|) where:

• n = number of words in dictionary
• l = average length of words
• q = number of search operations
• |Σ| = size of character set (26 for lowercase English letters)

Space Complexity:

• The trie stores all words from the dictionary
• In the worst case, if all words are completely different, we need O(n × l) nodes
• The recursive DFS call stack can go up to depth l during search, adding O(l) space
• Since O(n × l) > O(l) for any reasonable dictionary, the dominant factor is the trie storage

Overall space complexity: O(n × l) where:

• n = number of words in dictionary
• l = average length of words

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check Exact Match Without Modification

A critical pitfall is incorrectly handling the case where the search word exactly matches a dictionary word. The problem requires exactly one character change, so an exact match should return false.

Incorrect Implementation:

def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
    if index == len(word):
        return node.is_end  # Wrong! Doesn't check if we made exactly one change

Correct Implementation:

def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
    if index == len(word):
        return difference_count == 1 and node.is_end  # Must have exactly 1 difference

2. Inefficient Character Difference Exploration

Another common mistake is exploring all 26 possible characters when trying modifications, even when most don't exist in the trie. This leads to unnecessary recursion and performance degradation.

Inefficient Approach:

# Trying all 26 letters regardless of what's in the trie
if difference_count == 0:
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c != word[index] and c in node.children:
            if dfs(index + 1, node.children[c], 1):
                return True

Efficient Approach (as in the solution):

# Only iterate through characters that actually exist in the trie
return difference_count == 0 and any(
    dfs(index + 1, node.children[char], 1) 
    for char in node.children 
    if char != word[index]
)

3. Incorrect Difference Count Management

A subtle bug can occur when the difference count is incremented incorrectly or when allowing multiple changes.

Wrong Pattern:

def dfs(index: int, node: 'Trie', difference_count: int) -> bool:
    # ... base case ...
  
    # Bug: This allows unlimited changes
    for char in node.children:
        if dfs(index + 1, node.children[char], difference_count + (char != word[index])):
            return True
    return False

This implementation would incorrectly allow multiple character changes because it doesn't restrict exploration once a change has been made.

Correct Pattern: The solution correctly separates the logic:

• First, try the exact match path (no change)
• Then, only if no change has been made yet (difference_count == 0), try modification paths

4. Memory Inefficiency with Redundant Trie Nodes

While not a correctness issue, creating unnecessary Trie nodes for empty paths can waste memory. Always ensure nodes are created only when needed:

Wasteful:

def insert(self, word: str) -> None:
    current_node = self
    for char in word:
        current_node.children[char] = current_node.children.get(char, Trie())
        current_node = current_node.children[char]
    current_node.is_end = True

Memory-Efficient (as in the solution):

def insert(self, word: str) -> None:
    current_node = self
    for char in word:
        if char not in current_node.children:
            current_node.children[char] = Trie()
        current_node = current_node.children[char]
    current_node.is_end = True