Algorithm
Problem Name: 676. Implement Magic Dictionary
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.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class MagicDictionary {
public:
/** Initialize your data structure here. */
MagicDictionary() {}
/** Build a dictionary through a list of words */
void buildDict(vector<string> dict) {
for(auto x: dict) m[x.size()].push_back(x);
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
bool search(string word) {
for(auto x: m[word.size()])
if(oneEditDistance(x, word)) return true;
return false;
}
private:
unordered_map<int, vector < string>>m;
bool oneEditDistance(string& a, string& b){
int diff = 0;
for(int i = 0; i < a.size() && diff <= 1; i++)
if(a[i] != b[i]> diff++;
return diff == 1;
}
};
Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]
#2 Code Example with Java Programming
Code -
Java Programming
class MagicDictionary {
/** Initialize your data structure here. */
Set words;
Map < String, Integer> count;
public MagicDictionary() {
words = new HashSet<>();
count = new HashMap < >();
}
private List generalizedNeighbour(String word) {
List list = new ArrayList<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
char letter = chars[i];
chars[i] = '*';
String magic = new String(chars);
list.add(magic);
chars[i] = letter;
}
return list;
}
/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
for (String word : dict) {
words.add(word);
for (String neighbour : generalizedNeighbour(word)) {
count.put(neighbour, count.getOrDefault(neighbour, 0) + 1);
}
}
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
public boolean search(String word) {
for (String neighbour : generalizedNeighbour(word)) {
int c = count.getOrDefault(neighbour, 0);
if (c > 1 || c == 1 && !words.contains(word)) {
return true;
}
}
return false;
}
}
Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const MagicDictionary = function(dict) {
this.dict = [];
};
MagicDictionary.prototype.buildDict = function(dict) {
this.dict = dict;
};
MagicDictionary.prototype.search = function(word) {
return check(word, this.dict);
};
function check(str, arr) {
let el;
for (let i = 0; i < arr.length; i++) {
el = arr[i];
if (el.length === str.length && oneCharDiff(el, str)) {
return true;
}
}
return false;
}
function oneCharDiff(str1, str2) {
let diff = 0;
for (let i = 0; i < str1.length; i++) {
if (str1[i] !== str2[i]) {
diff += 1;
}
}
return diff === 1 ? true : false;
}
Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]
#4 Code Example with Python Programming
Code -
Python Programming
def __init__(self):
"""
Initialize your data structure here.
"""
from collections import defaultdict
self.var = defaultdict(set)
def buildDict(self, dict):
"""
Build a dictionary through a list of words
:type dict: List[str]
:rtype: void
"""
for w in dict:
for i in range(len(w)): self.var[(i, w[:i] + w[i + 1:])].add(w[i])
def search(self, word):
"""
Returns if there is any word in the trie that equals to the given word after modifying exactly one character
:type word: str
:rtype: bool
"""
for i in range(len(word)):
if self.var[(i, word[:i] + word[i + 1:])] - {word[i]}: return True
return False
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)
Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]