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.The key idea behind #676 Implement Magic Dictionary is to design a structure that stores words and allows searching for another word that differs by exactly one character. A common and efficient strategy is to use a Trie (prefix tree). The Trie stores all dictionary words, enabling efficient character-by-character traversal.
During search, you traverse the Trie while keeping track of whether a character modification has already been used. Using Depth-First Search (DFS), you try matching the current character and also explore alternatives when the modification has not yet been used. This allows checking all valid one-character substitutions efficiently.
An alternative approach uses a hash table with pattern transformations where each character position is replaced with a wildcard. However, the Trie + DFS approach scales well for repeated searches and maintains clear control over the single modification constraint. Building the dictionary is linear in the total characters, while search explores limited branches depending on the alphabet size.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Trie + DFS Search | Build: O(N * L), Search: O(26 * L) | O(N * L) |
| Hash Map with Wildcard Patterns | Build: O(N * L), Search: O(L) | O(N * L) |
ThePrimeTime
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of dictionary design and Trie-based search problems are common in FAANG-style interviews. They test knowledge of data structures, string manipulation, and search strategies like DFS.
A Trie (prefix tree) is one of the best data structures for this problem because it allows efficient prefix traversal and controlled branching when trying character substitutions.
Yes, another approach uses a hash map with wildcard patterns where each position in a word is replaced by a placeholder. This allows quick lookup to determine whether a word exists with exactly one character difference.
A common optimal approach uses a Trie combined with DFS. The Trie stores all dictionary words, and during search you explore possible character substitutions while ensuring only one modification is used.