/**
knakul853
**/
class Trie {

    public:
    Trie* children[26];
    bool leaf;

    Trie()
    {
           leaf = false;
         for(int i=0;i<26;i++)
             children[i] = NULL;
    }
};

class MagicDictionary {

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

    }

    void insert(string word)
    {
         Trie* node = root;

        int n = (int)word.size();
        for( int i=0;i < n; i++ )
        {
            char ch = word[i];

            if(!node->children[ch - 'a'])
                node->children[ch-'a'] = new Trie();
            node = node->children[ch-'a'];
        }

        node->leaf = true;
    }
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {

        int n = (int)dict.size();

        for( int i=0;i<n;i++ )
        {
            insert(dict[i]);
        }
    }

    bool found(string word)
    {
         Trie* node = root;

        for( char c: word )
        {
            if( !node->children[c-'a']) return false;

            node = node->children[c - 'a'];
        }

        return node->leaf;
    }

    /** Returns if there is any word in the trie that equals to the given word after modifying exactly                        one character */
    bool search(string word) {

        for(int i=0;i<(int)word.size(); i++)
        {
            char temp = word[i];

            for(char ch='a'; ch <='z'; ch++ )
            {
                word[i] = ch;
                if(ch == temp)continue;

                if( found(word)) return true;

            }

            word[i] = temp;
        }
        return false;


    }
};

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