Implement Magic Dictionary Solution in C++

Problem Description

So, you think you can just type any word and it will magically appear in your dictionary? Well, think again! The “Implement Magic Dictionary” problem on LeetCode is here to remind you that even in the world of programming, nothing is as simple as it seems. Imagine you’re trying to send a text to your friend, but autocorrect decides to play a prank on you. You type “hello,” and it changes it to “helloo.” Now, your friend thinks you’re either a ghost or just really bad at spelling.

In this problem, you need to create a magic dictionary that can help you find words that are almost correct. You can change exactly one character in a word to see if it matches any word in your dictionary. So, if you type “hello,” the dictionary should recognize that “hella” is close enough to be considered a match.

Code Solution


class MagicDictionary {
 public:
  void buildDict(vector 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 dict;

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

Approach

The approach taken in this solution is quite clever. The buildDict function constructs a dictionary where each word is stored in a way that allows for easy lookup of words that differ by one character. It does this by replacing each character in the word with a wildcard character (*) and storing the result in an unordered map. The search function then checks if a modified version of the search word exists in the dictionary, ensuring that the character at the replaced position is different from the original character.

Time and Space Complexity

Type	Complexity
Time Complexity	O(N * L)
Space Complexity	O(N * L)

Real-World Example

Imagine you’re at a coffee shop, and you order a “cappuccino.” The barista, however, hears “capuccino” and starts making that instead. When you get your drink, you realize it’s not what you wanted, but it’s close enough that you can still enjoy it. This is similar to how the magic dictionary works; it helps you find words that are almost right, just like how you might still enjoy that slightly misspelled coffee order.