Simple and high efficient C++ solution


  • 0

    Replace each character once at a time with a wildcard and store in a hash map with the replaced character being the value. If multiple word happens to be turned into same word-with-wildcard, the stored character is removed to indicate the case.
    search achieves a optimized O(len(word)) time complexity.

    class MagicDictionary {
    public:
        unordered_map<string, char> map;
    
        void buildDict(vector<string> dict) {
            for (string &word : dict) {
                for (int i = 0; i < word.size(); i++) {
                    string mw = word;
                    mw[i] = '*';
                    if (!map.count(mw))
                        map[mw] = word[i];
                    else if (map[mw] != word[i])
                        map[mw] = 0;
                }
            }
        }
        
        bool search(string word) {
            for (int i = 0; i < word.size(); i++) {
                string mw = word;
                mw[i] = '*';
                if (map.count(mw) && map[mw] != word[i])
                    return true;
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.