Implement Magic Dictionary
MedPrompt
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 stringsdictionary.bool search(String searchWord)Returnstrueif you can change exactly one character insearchWordto match any string in the data structure, otherwise returnsfalse.
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.- All the strings in
dictionaryare distinct. 1 <= searchWord.length <= 100searchWordconsists of only lower-case English letters.buildDictwill be called only once beforesearch.- At most
100calls will be made tosearch.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. We don't perform any special pre-processing in buildDict. We simply store the dictionary. When search is called, we iterate through every word in our stored dictionary and compare it with the searchWord. A helper function can be used to check if two words of the same length differ by exactly one character.
Algorithm
- In the
buildDictmethod, simply store the provideddictionaryarray in a member variable. - In the
search(searchWord)method:- Iterate through each
wordin the stored dictionary. - If the length of
wordis different fromsearchWord, skip to the next word. - If the lengths are the same, initialize a difference counter to zero.
- Compare
wordandsearchWordcharacter by character. - For each position where the characters do not match, increment the difference counter.
- After comparing all characters, if the difference counter is exactly 1, a match is found, so return
true. - If the loop completes without finding any word with exactly one difference, return
false.
- Iterate through each
Walkthrough
The buildDict method takes the array of strings and stores it, for instance, in a String[] or List<String>. The main logic resides in the search method. It performs a linear scan over all the words in the dictionary. For each dictionary word, it first checks if its length matches the searchWord's length. If they don't match, it's impossible for them to be one edit away, so we move to the next word. If the lengths are equal, we proceed to count the number of positions at which their characters differ. If this count is exactly one, we've found our 'magic' word and can immediately return true. If we iterate through the entire dictionary without finding such a word, we return false.
class MagicDictionary { private String[] dictionary; public MagicDictionary() { } public void buildDict(String[] dictionary) { this.dictionary = dictionary; } public boolean search(String searchWord) { for (String word : dictionary) { if (word.length() != searchWord.length()) { continue; } int diff = 0; for (int i = 0; i < word.length(); i++) { if (word.charAt(i) != searchWord.charAt(i)) { diff++; } } if (diff == 1) { return true; } } return false; }}Complexity
Time
`buildDict`: O(1) if we only store the reference, or O(D) if we copy the dictionary strings. `search`: O(N * L), where N is the number of words in the dictionary and L is the length of the `searchWord`. This is because we iterate through all N words and each comparison takes O(L) time.
Space
O(D), where D is the total number of characters in all words in the dictionary, to store the dictionary itself.
Trade-offs
Pros
Very simple to understand and implement.
Minimal time and space complexity for the
buildDictoperation.
Cons
The
searchoperation is inefficient, with a time complexity proportional to the total size of the dictionary.For large dictionaries, the search time can be prohibitive, although it passes within the given constraints.
This approach is an optimization over the naive brute-force method. The key idea is that a 'magic' match can only exist between words of the same length. We can leverage this by pre-processing the dictionary in buildDict to group words by their length. A HashMap is a suitable data structure for this, mapping a word length (Integer) to a list of words of that length.
Algorithm
- In
buildDict, initialize aHashMap<Integer, List<String>>. - Iterate through each
wordin the inputdictionary. - For each
word, get its length and add it to the list associated with that length in the HashMap. - In
search(searchWord):- Get the length of
searchWord, saylen. - Retrieve the list of candidate words from the HashMap using
lenas the key. - If no list exists for that key, return
false. - Iterate through the retrieved list of candidate words.
- For each candidate, count the character differences with
searchWord. - If the difference count is exactly 1, return
true. - If the loop finishes, return
false.
- Get the length of
Walkthrough
During the buildDict phase, we iterate through the dictionary and populate a HashMap<Integer, List<String>>. For each word, we use its length as the key and add the word to the list of words for that key. When search(searchWord) is called, we first determine the length of searchWord. Then, we use this length to directly access the list of all dictionary words that have the same length. This narrows down our search space significantly. We then iterate only over this smaller list of candidates, performing the same one-difference check as in the brute-force approach. If no words of the given length exist in our map, we can immediately return false.
class MagicDictionary { private Map<Integer, List<String>> map; public MagicDictionary() { map = new HashMap<>(); } public void buildDict(String[] dictionary) { for (String word : dictionary) { int len = word.length(); map.computeIfAbsent(len, k -> new ArrayList<>()).add(word); } } public boolean search(String searchWord) { int len = searchWord.length(); if (!map.containsKey(len)) { return false; } for (String word : map.get(len)) { int diff = 0; for (int i = 0; i < len; i++) { if (word.charAt(i) != searchWord.charAt(i)) { diff++; } } if (diff == 1) { return true; } } return false; }}Complexity
Time
`buildDict`: O(D), as we iterate through all characters of the dictionary once to build the map. `search`: O(K * L), where K is the number of words with the same length as `searchWord`, and L is the length. This is better than O(N * L) on average but has the same worst-case complexity.
Space
O(D), where D is the total number of characters in the dictionary, to store the HashMap.
Trade-offs
Pros
Improves the average-case performance of
searchby reducing the number of words to compare against.Still relatively simple to implement.
Cons
The worst-case time complexity for
searchis the same as the brute-force approach (when all dictionary words have the same length).Requires more space and pre-processing time in
buildDictcompared to the simple brute-force approach.
This approach trades off a slower, more memory-intensive buildDict phase for a much faster search operation. The core idea is to pre-compute all possible one-character variations of the dictionary words. We do this by creating 'generalized' words. For example, for the word "hello", we generate patterns like "ello", "hllo", "he*lo", etc. We store these patterns in a HashMap and count how many dictionary words map to each pattern.
Algorithm
- In
buildDict:- Initialize a
HashMap<String, Integer> countsand aHashSet<String> words. - For each
wordin thedictionary:- Add
wordto thewordsset. - For each character position
iinword, create a generalized pattern by replacing the character atiwith a wildcard (e.g., '*'). - Increment the count for this pattern in the
countsmap.
- Add
- Initialize a
- In
search(searchWord):- For each character position
iinsearchWord, create a generalized pattern. - Look up this pattern in the
countsmap to get its frequency,count. - A match is found if
count > 1. - A match is also found if
count == 1ANDsearchWordis not in the originalwordsset. - If a match is found, return
true. - If the loop finishes, return
false.
- For each character position
Walkthrough
In buildDict, we process each word from the dictionary. For a word of length L, we generate L different patterns by replacing each character, one by one, with a wildcard like '*'. We store these patterns as keys in a HashMap, and their values are the counts of how many dictionary words generate that specific pattern. We also store the original dictionary words in a HashSet for quick lookups.
When search(searchWord) is called, we apply the same generalization process. For each position in searchWord, we create a pattern and look it up in our HashMap. If the pattern exists, we check its count.
- If the count is greater than 1, it means at least two words in the dictionary match this pattern. Even if
searchWorditself is one of them, there's at least one other, so we have a valid magic match. - If the count is exactly 1, we must ensure the single dictionary word that matches this pattern is not
searchWorditself (as we need to change a character). We can verify this by checking ifsearchWordexists in our original dictionary HashSet. If it doesn't, the match is valid.
class MagicDictionary { private Set<String> words; private Map<String, Integer> counts; public MagicDictionary() { words = new HashSet<>(); counts = new HashMap<>(); } public void buildDict(String[] dictionary) { for (String word : dictionary) { this.words.add(word); for (int i = 0; i < word.length(); i++) { String pattern = word.substring(0, i) + "*" + word.substring(i + 1); counts.put(pattern, counts.getOrDefault(pattern, 0) + 1); } } } public boolean search(String searchWord) { for (int i = 0; i < searchWord.length(); i++) { String pattern = searchWord.substring(0, i) + "*" + searchWord.substring(i + 1); int count = counts.getOrDefault(pattern, 0); if (count > 1 || (count == 1 && !words.contains(searchWord))) { return true; } } return false; }}Complexity
Time
`buildDict`: O(N * L^2). For each of the N words, we generate L patterns, and each pattern generation takes O(L) time due to string manipulations. `search`: O(L^2). We generate L patterns for the `searchWord`, and each generation and lookup takes O(L) time.
Space
O(N * L^2), where N is the number of words and L is their maximum length. This is because we can have up to N*L generalized words, each of length L.
Trade-offs
Pros
Extremely fast
searchoperation, with a time complexity that depends only on the length of the word, not the size of the dictionary.This is the most efficient approach when
searchis called many times.
Cons
The
buildDictmethod is significantly more complex and time-consuming.Requires a large amount of space to store all the generalized word patterns, O(N * L^2).
Solutions
Solution
class Trie { private Trie [] children = new Trie [ 26 ]; private boolean isEnd ; public void insert ( String w ) { Trie node = this ; for ( char c : w . toCharArray ()) { int i = c - 'a' ; if ( node . children [ i ] == null ) { node . children [ i ] = new Trie (); } node = node . children [ i ]; } node . isEnd = true ; } public boolean search ( String w ) { return dfs ( w , 0 , this , 0 ); } private boolean dfs ( String w , int i , Trie node , int diff ) { if ( i == w . length ()) { return diff == 1 && node . isEnd ; } int j = w . charAt ( i ) - 'a' ; if ( node . children [ j ] != null ) { if ( dfs ( w , i + 1 , node . children [ j ], diff )) { return true ; } } if ( diff == 0 ) { for ( int k = 0 ; k < 26 ; k ++) { if ( k != j && node . children [ k ] != null ) { if ( dfs ( w , i + 1 , node . children [ k ], 1 )) { return true ; } } } } return false ; } } class MagicDictionary { private Trie trie = new Trie (); public MagicDictionary () { } public void buildDict ( String [] dictionary ) { for ( String w : dictionary ) { trie . insert ( w ); } } public boolean search ( String searchWord ) { return trie . search ( searchWord ); } } /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dictionary); * boolean param_2 = obj.search(searchWord); */class Trie { private: Trie * children [ 26 ]; bool isEnd = false ; public: Trie () { fill ( begin ( children ), end ( children ), nullptr ); } void insert ( const string & w ) { Trie * node = this ; for ( char c : w ) { int i = c - 'a' ; if ( ! node -> children [ i ]) { node -> children [ i ] = new Trie (); } node = node -> children [ i ]; } node -> isEnd = true ; } bool search ( const string & w ) { function < bool ( int , Trie * , int ) > dfs = [ & ]( int i , Trie * node , int diff ) { if ( i >= w . size ()) { return diff == 1 && node -> isEnd ; } int j = w [ i ] - 'a' ; if ( node -> children [ j ] && dfs ( i + 1 , node -> children [ j ], diff )) { return true ; } if ( diff == 0 ) { for ( int k = 0 ; k < 26 ; ++ k ) { if ( k != j && node -> children [ k ]) { if ( dfs ( i + 1 , node -> children [ k ], 1 )) { return true ; } } } } return false ; }; return dfs ( 0 , this , 0 ); } }; class MagicDictionary { public: MagicDictionary () { trie = new Trie (); } void buildDict ( vector < string > dictionary ) { for ( auto & w : dictionary ) { trie -> insert ( w ); } } bool search ( string searchWord ) { return trie -> search ( searchWord ); } private: Trie * trie ; }; /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary* obj = new MagicDictionary(); * obj->buildDict(dictionary); * bool param_2 = obj->search(searchWord); */class Trie : __slots__ = [ "children" , "is_end" ] def __init__ ( self ): self . children = {} self . is_end = False def insert ( self , w : str ) -> None : node = self for c in w : if c not in node . children : node . children [ c ] = Trie () node = node . children [ c ] node . is_end = True def search ( self , w : str ) -> bool : def dfs ( i : int , node : Trie , diff : int ) -> bool : if i == len ( w ): return diff == 1 and node . is_end if w [ i ] in node . children and dfs ( i + 1 , node . children [ w [ i ]], diff ): return True return diff == 0 and any ( dfs ( i + 1 , node . children [ c ], 1 ) for c in node . children if c != w [ i ] ) return dfs ( 0 , self , 0 ) class MagicDictionary : def __init__ ( self ): self . trie = Trie () def buildDict ( self , dictionary : List [ str ]) -> None : for w in dictionary : self . trie . insert ( w ) def search ( self , searchWord : str ) -> bool : return self . trie . search ( searchWord ) # Your MagicDictionary object will be instantiated and called as such: # obj = MagicDictionary() # obj.buildDict(dictionary) # param_2 = obj.search(searchWord)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.