Leetcode 676. Implement Magic Dictionary

Problem Explanation

The problem is about implementing a class named MagicDictionary with two methods: buildDict and search.

• The buildDict method takes in a list of non-repetitive words to build a dictionary.

• The search method takes in a word and checks to see if by modifying exactly one character in the word, the modified word exists in the dictionary we've built previously.

It's worth noting that we consider only lowercase letters a-z for all the inputs.

The problem revolves around designing these methods such that they work correctly according to these constraints. Because we are dealing with strings and need to make several efficient searches or lookups, a good data structure to consider might be a hash table/dictionary that offers average constant time complexity for search operations.

For example, if we build a dictionary with the words "hello" and "leetcode", then searching "hhllo" should return True because changing one character in "hhllo" (changing 'h' to 'e') results in "hello", which is in our dictionary. However, searching "hello" should return False as there is no other word in the dictionary that can be formed by modifying exactly one character from "hello".

Solution Approach

The solution uses a dictionary(dict). In the buildDict method, we iterate over each word in the dictionary list and for each word, we iterate again over its length. For each character in the word, we create a string by replacing that character with '*'. This string serves as a key which maps to the replaced character in the dictionary.

In the search method, we again replace each character in the search word with '*', and check if the replaced string exists as a key in our dictionary. If it does, we then check if the mapped character corresponds to the same character in the search word. If it doesn't, we return True, because this means we've found a word which matches the search word except for one character. If no such occurrence is found, we finally return False.

Python Solution

1
2python
3class MagicDictionary(object):
4
5    def __init__(self):
6        self.dictionary = collections.defaultdict(set)
7
8    def buildDict(self, dictionary):
9        """
10        :type dictionary: List[str]
11        :rtype: None
12        """
13        for word in dictionary:
14            for i, char in enumerate(word):
15                key = word[:i] + '*' + word[i+1:]
16                self.dictionary[key].add(char)
17
18    def search(self, searchWord):
19        """
20        :type searchWord: str
21        :rtype: bool
22        """
23        for i, char in enumerate(searchWord):
24            key = searchWord[:i] + '*' + searchWord[i+1:]
25            if self.dictionary[key] - {char}:
26                return True
27        return False

Java Solution

1
2java
3public class MagicDictionary {
4    Map<String, Character> dict;
5    public MagicDictionary() {
6        dict = new HashMap<>();
7    }
8
9    public void buildDict(String[] dictionary) {        
10        for (String word : dictionary) {
11            for (int i = 0; i < word.length(); i++) {
12                String s = getReplaced(word, i);
13                dict.put(s, dict.containsKey(s)? '*': word.charAt(i));
14            }
15        }
16    }
17
18    public boolean search(String searchWord) {
19        for (int i = 0; i < searchWord.length(); i++) {
20            String s = getReplaced(searchWord, i);
21            if (dict.containsKey(s) && dict.get(s) != searchWord.charAt(i)) {
22                return true;
23            }
24        }
25        return false;
26    }
27
28    private String getReplaced(String s, int i) {
29        return s.substring(0, i) + '*' + s.substring(i + 1);
30    }
31}

JavaScript Solution

1
2javascript
3var MagicDictionary = function() {
4    this.dictionary = new Map();
5};
6
7MagicDictionary.prototype.buildDict = function(dictionary) {
8    for (let word of dictionary) {
9        for (let i = 0; i < word.length; i++) {
10            let replaced = word.slice(0, i) + '*' + word.slice(i + 1);
11            this.dictionary.set(replaced, this.dictionary.has(replaced) ? '*' : word[i]);
12        }
13    }
14};
15
16MagicDictionary.prototype.search = function(searchWord) {
17    for (let i = 0; i < searchWord.length; i++) {
18        let replaced = searchWord.slice(0, i) + '*' + searchWord.slice(i + 1);
19        if (this.dictionary.has(replaced) && this.dictionary.get(replaced) !== searchWord[i]) {
20            return true;
21        }
22    }
23    return false;
24};

C++ Solution

1
2cpp
3class MagicDictionary {
4    unordered_map<string, char> dict;
5    string getReplaced(const string& s, int i) {
6        return s.substr(0, i) + '*' + s.substr(i + 1);
7    }
8public:
9    /** Initialize your data structure here. */
10    MagicDictionary() {
11    }
12    
13    void buildDict(vector<string> dictionary) {
14        for (const string& word : dictionary)
15            for (int i = 0; i < word.length(); ++i) {
16                const string replaced = getReplaced(word, i);
17                dict[replaced] = dict.count(replaced) ? '*' : word[i];
18            }
19    }
20    
21    bool search(string searchWord) {
22        for (int i = 0; i < searchWord.length(); ++i) {
23            const string replaced = getReplaced(searchWord, i);
24            auto it = dict.find(replaced);
25            if (it != end(dict) && it->second != searchWord[i])
26                return true;
27        }
28        return false;
29    }
30};

C# Solution

1
2csharp
3public class MagicDictionary {
4    Dictionary<string, char> dict = new Dictionary<string, char>();
5    
6    public void BuildDict(string[] dictionary) {
7        foreach (string word in dictionary) {                
8            for (int i = 0; i < word.Length; i++) {
9                string replaced = word.Substring(0, i) + '*' + word.Substring(i+1);
10                if(dict.ContainsKey(replaced)) 
11                    dict[replaced] = '*';
12                else 
13                    dict[replaced] = word[i];
14            }
15        }
16    }
17    
18    public bool Search(string searchWord) {
19        for (int i = 0; i < searchWord.Length; i++) {
20            string replaced = searchWord.Substring(0, i) + '*' + searchWord.Substring(i+1);
21            if (dict.ContainsKey(replaced) && dict[replaced] != searchWord[i])
22                return true;
23        }
24        return false;
25    }
26}

This solution creates a unique mapping for each possible single modified word to its replaced character. When the search method is called, it replaces each character in the search word and checks if there is a word which matches except for that character.This approach makes the search process quick and efficient since it directly looks up the potential matches in the dictionary instead of iterating over all the words. This would be a significant time saver especially when the dictionary size is large.

Time Complexity Analysis

The time complexity of the buildDict method is O(n*m) where n is the number of words and m is the average length of the words in dictionary list. For each word, we need to create m different manifolds by replacing each character.

The time complexity of search is also O(m) where m is the length of the search word. We create manifolds by replacing each character and check if the replaced word exists in the dictionary and the replaced character is not equal to the original character.

The space complexity is also approximately O(n*m) as for each word, m different manifolds are stored.

This solution to implement MagicDictionary is swift and efficient because it creates unique keys in memory to facilitate quick lookups. It is ideal when working with a large dictionary or performing frequent search operations. However, when the size of the dictionary or the words in it get excessively large, this solution might use a lot of memory. Therefore, according to your problem and the resources it demands, one must choose the optimal approach.