Implement Magic Dictionary

Implement Magic Dictionary

What is this problem about?

The Implement Magic Dictionary coding problem asks you to design a data structure that stores a set of words and provides a "magic" search function. The search(word) function returns true if and only if you can change exactly one character in the input word to make it equal to one of the words already in the dictionary.

Why is this asked in interviews?

Google and Bloomberg use this to test your ability to modify standard search algorithms. It evaluation your understanding of Trie interview patterns and Hash Table interview patterns. The "exactly one change" constraint is a clever twist that prevents you from using simple set lookups, forcing you to explore the search space of nearby strings or traverse a tree with a "mistake" allowance.

Algorithmic pattern used

There are two main approaches:

1. Hash Table with Length Grouping: Store words in a map keyed by their length. When searching, only compare the input word against stored words of the same length. For each comparison, count the character mismatches. If any word has exactly 1 mismatch, return true.
2. Trie with DFS: Store words in a Trie. During the search, perform a DFS. Keep a boolean modified. If you encounter a character mismatch and modified is false, proceed to the children by treating the mismatch as your one allowed change.

Example explanation

Dictionary: ["hello", "hallo", "leetcode"]

1. search("hello"):
   • Compare with "hello": 0 differences (Invalid, must be exactly 1).
   • Compare with "hallo": 1 difference ('e' vs 'a'). True!
2. search("hell"):
   • Length mismatch with all words. False.
3. search("hellp"):
   • 1 difference with "hello". True!

Common mistakes candidates make

• Exact Match: Returning true if the word exists perfectly in the dictionary. The problem explicitly requires a modification.
• Length Inconsistency: Forgetting that changing one character never changes the length of the string.
• DFS without Pruning: In the Trie approach, not stopping the search branch if more than one mistake has been made.

Interview preparation tip

This is essentially a "Hamming Distance of 1" problem. If the dictionary is small, the length-grouped Hash Map is easier to write. If the dictionary is huge, the Trie DFS is more efficient because it shares prefixes and prunes search paths early.