Implement Magic Dictionary
Medium · Tries · Hash Table · String · Depth-First Search · Design · Trie
Problem
Design a dictionary that checks whether a word is exactly one letter change away from a stored word.
Implement MagicDictionary:
- MagicDictionary() creates the object.
- buildDict(dictionary) loads a list of distinct words.
- search(searchWord) returns true if you can change exactly one letter of searchWord to a different letter so that it equals some stored word, and false otherwise. A word identical to a stored word does not count on its own, because zero letters would change.
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: ops = ["MagicDictionary","buildDict","search","search","search","search"], args = [[],[["game","code"]],["gate"],["game"],["cone"],["codes"]] Output: [null,null,true,false,true,false]
"gate" and "cone" differ from a stored word in one position; "game" differs in none, and "codes" has the wrong length.
Input: ops = ["MagicDictionary","buildDict","search","search"], args = [[],[["ab","bb"]],["ab"],["cb"]] Output: [null,null,true,true]
"ab" is stored itself, but changing its a to b gives "bb", which is also stored.
Constraints
- 1 <= len(dictionary) <= 100
- 1 <= len(dictionary[i]), len(searchWord) <= 100
- All words are lowercase English letters
- All words in dictionary are distinct
- buildDict is called once, before any search
- At most 100 calls are made to search
Approaches
- Compare with every stored word — time buildDict O(N), search O(N · L), space O(N · L)
Follow-up
A trie works too: walk the search word down the trie, allowing exactly one step onto a different letter, and accept when you finish at the end of a word having used that one change. It shares prefixes between stored words, which saves memory when many words start the same way.
Related problems
Start free on Cariara · Coding problems · System design studio
