## 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 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 <= 100`
• `1 <= dictionary[i].length <= 100`
• `dictionary[i]` consists of only lower-case English letters.
• All the strings in `dictionary` are distinct.
• `1 <= searchWord.length <= 100`
• `searchWord` consists of only lower-case English letters.
• `buildDict` will be called only once before `search`.
• At most `100` calls will be made to `search`.

## 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;
}
};
``````
Copy The Code &

Input

cmd
["MagicDictionary", "buildDict", "search", "search", "search", "search"] [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]

Output

cmd
[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);
chars[i] = letter;
}
return list;
}

/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
for (String word : dict) {
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;
}
}
``````
Copy The Code &

Input

cmd
["MagicDictionary", "buildDict", "search", "search", "search", "search"] [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]

Output

cmd
[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;
}
``````
Copy The Code &

Input

cmd
["MagicDictionary", "buildDict", "search", "search", "search", "search"] [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]

Output

cmd
[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)
``````
Copy The Code &

Input

cmd
["MagicDictionary", "buildDict", "search", "search", "search", "search"] [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]

Output

cmd
[null, null, false, true, false, false]