Implement Magic Dictionary - Solution & Explanation

Q: Is Implement Magic Dictionary easy or hard?

Implement Magic Dictionary is rated Medium because the brute-force idea is straightforward but the optimal solution requires recognizing the wildcard pattern trick. Understanding how to convert a one-character difference rule into a hash lookup is the key insight.

Q: Implement Magic Dictionary Python/Java solution

Python and Java implementations typically build a HashMap or dictionary where keys are wildcard patterns like 'h*llo'. During search, the algorithm generates patterns for the query word and checks the map for matches while ensuring exactly one character difference.

Q: How to solve Implement Magic Dictionary in O(n)?

The practical optimal solution is O(n*m) preprocessing and O(m) search using a hash map of wildcard patterns. Each word produces m patterns by replacing one character with '*'. During search, matching patterns quickly identify words that differ by exactly one character.

Q: What is the best approach for Implement Magic Dictionary?

The hash map wildcard pattern approach is the most efficient and commonly expected solution. Each dictionary word generates patterns by replacing one character with '*', which are stored in a hash table. During search, the query word generates the same patterns and checks for matches in O(m) time after O(n*m) preprocessing.

Q: Is Implement Magic Dictionary asked at Google/Amazon/Meta?

Design-style dictionary problems and string mutation checks appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test hash table usage, string manipulation, and data structure design concepts similar to Magic Dictionary.

Q: What data structure is used in Implement Magic Dictionary?

The most common solution uses a hash table that maps wildcard string patterns to counts or lists of dictionary words. Alternatives may use tries or direct string comparison, but the hash map pattern technique provides the best balance of simplicity and performance.

Q: What is the time complexity of Implement Magic Dictionary?

Using the optimized hash map pattern approach, building the dictionary takes O(n*m) time where n is the number of words and m is the word length. Each search operation runs in O(m) because only m wildcard patterns are generated and checked in a hash table.

MediumHash Table String Depth-First Search Design24 min readAsked at: Google, Bloomberg

Practice this problem

Problem Statement

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

MagicDictionary() Initializes the object.
void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:

Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]

Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // return False
magicDictionary.search("hhllo"); // We can change the second 'h' to 'e' to match "hello" so we return True
magicDictionary.search("hell"); // return False
magicDictionary.search("leetcoded"); // return False

Constraints:

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lower-case English letters.
All the strings in dictionary are distinct.
1 <= searchWord.length <= 100
searchWord consists of only lower-case English letters.
buildDict will be called only once before search.
At most 100 calls will be made to search.

Approach Overview

Problem Overview: Design a data structure that stores a dictionary of words and supports a search operation that returns true only if you can modify exactly one character of the input word to match a stored word. Exact matches are not allowed; the match must differ by exactly one position.

Approach 1: Brute-force Comparison (Build: O(n*m), Search: O(n*m), Space: O(n*m))

Store all dictionary words in a list or set. During search, iterate through every stored word and compare it with the query character by character. Count how many positions differ. If exactly one character differs, return true. If the difference is zero or more than one, continue checking other words.

This approach relies purely on direct string comparison and works because the constraint "exactly one modification" can be verified by scanning both strings simultaneously. The downside is that every query potentially scans the entire dictionary. With n words of length m, the search cost becomes O(n*m). It’s simple and acceptable for small dictionaries but scales poorly.

Approach 2: Hash Map for Character Patterns (Build: O(n*m), Search: O(m), Space: O(n*m))

Precompute wildcard patterns for each dictionary word. For every position in a word, replace that character with a placeholder such as *. For example, the word hello generates patterns like *ello, h*llo, he*lo, hel*o, and hell*. Store these patterns in a hash table that maps each pattern to the number of words that produce it.

During search, generate the same patterns for the query word and check if any pattern exists in the hash map. A matching pattern means there is a dictionary word differing by one character at that position. Additional checks ensure the match isn't the same word when only one dictionary entry produces the pattern.

The key insight is transforming the "one character difference" rule into shared wildcard patterns. Each lookup becomes a constant-time hash operation. Since only m patterns are generated for a word of length m, search runs in O(m) time after preprocessing. This approach heavily leverages string manipulation and efficient hash table lookups.

Recommended for interviews: The hash map pattern approach is what most interviewers expect. It shows you can convert a character-difference constraint into a pattern indexing problem and optimize lookups using hashing. Explaining the brute-force comparison first demonstrates clear reasoning about the problem, while the optimized design highlights strong data structure skills commonly tested in design-style questions.

Approach 1: Brute-force Comparison

This approach iterates over each word in the dictionary and compares it to the search word by changing exactly one character at a time. If any change results in a match, the search returns true.

In this solution, we define the MagicDictionary structure to store words and compare each word with searchWord. If there is exactly one different character, we return true.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of words and m is the average word length. Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Hash Map for Character Patterns

We optimize search by utilizing hash maps to store patterns for similar length words with one character removed at each position. During the search check, modified search word patterns are created and checked against stored patterns.

This C solution uses a hash-like approach by storing patterns with one wildcard character, facilitating a faster search. Patterns are checked against the search word with single character modifications.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n + m), where n represents the number of words and m represents the search length. Space Complexity: O(n * m).

Try this approach in the editor →

Approach 3: Trie + DFS

We can use a trie to store all the words in the dictionary. For each word we search, we use depth-first search. Specifically, we start from the root of the trie. For the current letter we are traversing, we first check whether there is a child node that is the same as it. If there is, we continue to traverse downwards. Otherwise, we need to check whether there are remaining modification times. If not, it means that it cannot be matched, so we return false. If there are remaining modification times, we can try to modify the current letter and continue to traverse downwards. If the child node corresponding to the modified letter exists, it means that it can be matched, otherwise it means that it cannot be matched, so we return false. If we traverse to the end of the word and the number of modifications is exactly 1, it means that it can be matched, so we return true.

The time complexity is O(n times l + q times l times |\Sigma|), and the space complexity is O(n times l), where n and l are the number of words in the dictionary and the average length of the words, respectively, and q is the number of words searched. In addition, |\Sigma| represents the size of the character set. Here, the character set is lowercase English letters, so |\Sigma|=26.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Brute-force Comparison	Time Complexity: O(n * m), where n is the number of words and m is the average word length. Space Complexity: O(1).
Hash Map for Character Patterns	Time Complexity: O(n + m), where n represents the number of words and m represents the search length. Space Complexity: O(n * m).
Trie + DFS	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute-force Comparison	Build: O(nm), Search: O(nm)	O(n*m)	Small dictionaries or quick prototype where implementation simplicity matters more than speed
Hash Map for Character Patterns	Build: O(n*m), Search: O(m)	O(n*m)	General case and interview settings where fast query time is required

Video Solution

花花酱 LeetCode 676. Implement Magic Dictionary - 刷题找工作 EP49 • Hua Hua • 3,725 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Implement Magic Dictionary easy or hard?

Implement Magic Dictionary is rated Medium because the brute-force idea is straightforward but the optimal solution requires recognizing the wildcard pattern trick. Understanding how to convert a one-character difference rule into a hash lookup is the key insight.

Implement Magic Dictionary Python/Java solution

Python and Java implementations typically build a HashMap or dictionary where keys are wildcard patterns like 'h*llo'. During search, the algorithm generates patterns for the query word and checks the map for matches while ensuring exactly one character difference.

How to solve Implement Magic Dictionary in O(n)?

The practical optimal solution is O(n*m) preprocessing and O(m) search using a hash map of wildcard patterns. Each word produces m patterns by replacing one character with '*'. During search, matching patterns quickly identify words that differ by exactly one character.

What is the best approach for Implement Magic Dictionary?

The hash map wildcard pattern approach is the most efficient and commonly expected solution. Each dictionary word generates patterns by replacing one character with '*', which are stored in a hash table. During search, the query word generates the same patterns and checks for matches in O(m) time after O(n*m) preprocessing.

Is Implement Magic Dictionary asked at Google/Amazon/Meta?

Design-style dictionary problems and string mutation checks appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test hash table usage, string manipulation, and data structure design concepts similar to Magic Dictionary.

What data structure is used in Implement Magic Dictionary?

The most common solution uses a hash table that maps wildcard string patterns to counts or lists of dictionary words. Alternatives may use tries or direct string comparison, but the hash map pattern technique provides the best balance of simplicity and performance.

What is the time complexity of Implement Magic Dictionary?

Using the optimized hash map pattern approach, building the dictionary takes O(n*m) time where n is the number of words and m is the word length. Each search operation runs in O(m) because only m wildcard patterns are generated and checked in a hash table.

Ready to solve this problem?

Practice Implement Magic Dictionary with our built-in code editor and test cases.

Practice on FleetCode

Implement Trie (Prefix Tree)

Longest Word in Dictionary

Problem Info

DifficultyMedium

Acceptance57.8%

Approaches3

Reading time24 min

Asked at

Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Brute-force Comparison

Code

Complexity

Approach 2: Hash Map for Character Patterns

Code

Complexity

Approach 3: Trie + DFS

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents