algoadvance

Leetcode 676. Implement Magic Dictionary

Problem Statement

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:

Clarifying Questions

  1. Input Scope:
    • Can dictionary contain duplicate words?
    • How large can the dictionary and the searchWord be?
  2. Character Set:
    • Are the words in the dictionary and the searchWord composed of only lowercase English letters?
  3. Functionality:
    • Should buildDict overwrite the existing dictionary or extend it?

Assuming the dictionary contains only unique words composed of lowercase English letters, and buildDict overwrites the existing dictionary.

Strategy

  1. Data Storage: Store each word in a set for quick look-up.
  2. Checking Transformations: To determine if you can convert searchWord into a dictionary word by changing exactly one character:
    • For each word in the dictionary with the same length as searchWord, compare the words character by character.
    • Count the number of differing characters. If exactly one character differs, return true.
  3. Optimizations:
    • Use a hashmap where the key is the length of the words. This allows fast access to only those words in the dictionary which have the same length as the searchWord when searching.

Code

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class MagicDictionary {
private:
    unordered_map<int, unordered_set<string>> dictionaryMap;

public:
    MagicDictionary() {
    }

    void buildDict(vector<string> dictionary) {
        dictionaryMap.clear();
        for (const string& word : dictionary) {
            dictionaryMap[word.size()].insert(word);
        }
    }

    bool search(string searchWord) {
        int wordLength = searchWord.size();
        if (dictionaryMap.find(wordLength) == dictionaryMap.end()) {
            return false;
        }

        for (const string& word : dictionaryMap[wordLength]) {
            int diffCount = 0;
            for (int i = 0; i < wordLength; ++i) {
                if (searchWord[i] != word[i]) {
                    ++diffCount;
                }
                if (diffCount > 1) {
                    break;
                }
            }
            if (diffCount == 1) {
                return true;
            }
        }
        return false;
    }
};

Time Complexity

  1. Build Dictionary: O(n) where n is the total number of characters in the dictionary (since we insert each word into the map).
  2. Search: O(m * k) where m is the size of the searchWord and k is the number of words in the dictionary that have the same length as searchWord (since we check each word of the same length character by character).

This approach ensures efficient look-up by leveraging a hashmap and reduces unnecessary comparisons by focusing only on words of the same length.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI