676

class Trie{
public:
    Trie* children[26];
    bool end;
    Trie(){
        for(int i=0; i<26; i++)
            children[i] = NULL;
        end = false;
    }
};

class MagicDictionary {
private:
    Trie* root = new Trie();
public:
    /** Initialize your data structure here. */
    MagicDictionary() {

    }
    void insert(string s){
        Trie* node = root;
        for(char c : s){
            if(!node -> children[c - 'a']){
                node -> children[c - 'a'] = new Trie();
            }
            node  = node -> children[c - 'a'];
        }
        node -> end = true;
    }

    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(int i = 0; i < dict.size(); i++){
            insert(dict[i]);
        }
    }

    bool found(Trie *node, string s, int idx, int change){
        if(idx == s.length() && change && node->end)
            return true;
        else if(idx == s.length())
            return false;

        int ch = s[idx]-'a';
        if(change){
            if(node->children[ch])
                return found(node->children[ch], s, idx+1, change);
            return false;
        }
        else{
            if(node->children[ch] && found(node->children[ch], s, idx+1, 0))
                return true;
            for(int i=0; i<26; i++){
                if(i == ch) continue;
                bool ans = false;
                if(node->children[i])
                    ans = found(node->children[i], s, idx+1, 1);
                if(ans) return true;
            }
            return false;
        }
        return false;
    }

    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        return found(root, word, 0, 0);
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dict);
 * bool param_2 = obj->search(word);
 */


------------------------

class MagicDictionary {
public:
    unordered_map<int, vector<string>> memo;

    /** Initialize your data structure here. */
    MagicDictionary() {
        memo.clear();
    }

    void buildDict(vector<string> dictionary) {
        for (auto & word : dictionary) {
            memo[word.size()].push_back(word);
        }
    }

    bool search(string searchWord) {
        int size = searchWord.size();

        if (memo.count(size) == 0)
            return 0;

        for (auto & word : memo[size]) {
            int cnt = 0;
            for (int i = 0; i < size; ++i) {
                if (word[i] != searchWord[i]) {
                    cnt++;
                    if (cnt > 1) break;
                }
            }
            if (cnt == 1)
                return true;
        }
        return false;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */