676. Implement Magic Dictionary LeetCode Solution

In this guide, you will get 676. Implement Magic Dictionary LeetCode Solution with the best time and space complexity. The solution to Implement Magic Dictionary problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Implement Magic Dictionary solution in C++
Implement Magic Dictionary solution in Java
Implement Magic Dictionary solution in Python
Additional Resources

676. Implement Magic Dictionary LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(|\texttt{searchWord}|^2)
Space Complexity: O(\Sigma |\texttt{dictionary[i]}|)

676. Implement Magic Dictionary LeetCode Solution in C++

class MagicDictionary {
 public:
  void buildDict(vector<string> dictionary) {
    for (const string& word : dictionary)
      for (int i = 0; i < word.length(); ++i) {
        const string replaced = getReplaced(word, i);
        dict[replaced] = dict.contains(replaced) ? '*' : word[i];
      }
  }

  bool search(string searchWord) {
    for (int i = 0; i < searchWord.length(); ++i) {
      const string replaced = getReplaced(searchWord, i);
      if (const auto it = dict.find(replaced);
          it != dict.cend() && it->second != searchWord[i])
        return true;
    }
    return false;
  }

 private:
  unordered_map<string, char> dict;

  string getReplaced(const string& s, int i) {
    return s.substr(0, i) + '*' + s.substr(i + 1);
  }
};
/* code provided by PROGIEZ */

676. Implement Magic Dictionary LeetCode Solution in Java

class MagicDictionary {
  public void buildDict(String[] dictionary) {
    for (final String word : dictionary)
      for (int i = 0; i < word.length(); ++i) {
        final String replaced = getReplaced(word, i);
        dict.put(replaced, dict.containsKey(replaced) ? '*' : word.charAt(i));
      }
  }

  public boolean search(String searchWord) {
    for (int i = 0; i < searchWord.length(); ++i) {
      final String replaced = getReplaced(searchWord, i);
      if (dict.getOrDefault(replaced, searchWord.charAt(i)) != searchWord.charAt(i))
        return true;
    }
    return false;
  }

  private Map<String, Character> dict = new HashMap<>();

  private String getReplaced(final String s, int i) {
    return s.substring(0, i) + '*' + s.substring(i + 1);
  }
}
// code provided by PROGIEZ

676. Implement Magic Dictionary LeetCode Solution in Python

class MagicDictionary:
  def __init__(self):
    self.dict = {}

  def buildDict(self, dictionary: list[str]) -> None:
    for word in dictionary:
      for i, c in enumerate(word):
        replaced = self._getReplaced(word, i)
        self.dict[replaced] = '*' if replaced in self.dict else c

  def search(self, searchWord: str) -> bool:
    for i, c in enumerate(searchWord):
      replaced = self._getReplaced(searchWord, i)
      if self.dict.get(replaced, c) != c:
        return True
    return False

  def _getReplaced(self, s: str, i: int) -> str:
    return s[:i] + '*' + s[i + 1:]
 # code by PROGIEZ