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 <= 1001 <= dictionary[i].length <= 100dictionary[i] consists of only lower-case English letters.dictionary are distinct.1 <= searchWord.length <= 100searchWord consists of only lower-case English letters.buildDict will be called only once before search.100 calls will be made to search.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.
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.
Time Complexity: O(n * m), where n is the number of words and m is the average word length. Space Complexity: O(1).
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.
Time Complexity: O(n + m), where n represents the number of words and m represents the search length. Space Complexity: O(n * m).
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.
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-force Comparison | Build: O(n*m), Search: O(n*m) | 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 |
花花酱 LeetCode 676. Implement Magic Dictionary - 刷题找工作 EP49 • Hua Hua • 3,721 views views
Watch 9 more video solutions →Practice Implement Magic Dictionary with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor