C++ trie solution
updated 2020/09/15\nThe original code can\'t pass OJ anymore. Please see updated code below.\n\nclass Node{\npublic:\n    vector<Node*> next;\n    bool isWord;\
`updated 2020/09/15`\nThe original code can\'t pass OJ anymore. Please see updated code below.\n```\nclass Node{\npublic:\n    vector<Node*> next;\n    bool isWord;\n    Node(){\n        isWord = false;\n        next = vector<Node*>(26, NULL);\n    }\n};\n\nclass Trie{\nprivate:\n    Node* root;\npublic:\n    Trie(){\n        root = new Node();\n    }\n    void insert(string s){\n        Node* cur = root;\n        for(char c: s){\n            if(cur->next[c - \'a\'] == NULL)\n                cur->next[c - \'a\'] = new Node();\n            cur = cur->next[c - \'a\'];\n        }\n        cur->isWord = true;\n    }\n    \n    bool find(string s){\n        Node* cur = root;\n        for(char c: s){\n            if(cur->next[c - \'a\'] == NULL)\n                return false;\n            cur = cur->next[c - \'a\'];\n        }\n        return cur->isWord;\n    }\n};\n\nclass MagicDictionary {\npublic:\n    /** Initialize your data structure here. */\n    MagicDictionary() {\n        trie = new Trie();\n    }\n    \n    /** Build a dictionary through a list of words */\n    void buildDict(vector<string> dict) {\n        for(string s: dict){\n            trie->insert(s);\n        }\n    }\n    \n    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */\n    bool search(string word) {\n        for(int i = 0; i < word.size(); i++){\n            for(int j = 0; j < 26; j++){\n                char c = j + \'a\';\n                if(c == word[i]) continue;\n                char oriChar = word[i];\n                word[i] = c;\n                if(trie->find(word))\n                    return true;\n                word[i] = oriChar;\n            }\n        }\n        return false;\n    }\nprivate:\n    Trie* trie;\n};\n ```\n \n`updated 2020/09/15`\nThe OJ has changed the time limit, so my original code can\'t pass.\nI updated my code to do dfs to optimize.\n```\nclass Node{\npublic:\n    vector<Node*> next;\n    bool isWord;\n    Node(){\n        isWord = false;\n        next = vector<Node*>(26, NULL);\n    }\n};\n\nclass Trie{\nprivate:\n    Node* root;\npublic:\n    Trie(){\n        root = new Node();\n    }\n    void insert(string s){\n        Node* cur = root;\n        for(char c: s){\n            if(cur->next[c - \'a\'] == NULL)\n                cur->next[c - \'a\'] = new Node();\n            cur = cur->next[c - \'a\'];\n        }\n        cur->isWord = true;\n    }\n    \n    bool find(string s, int cur_idx, int change = 0, Node* cur = NULL) {\n        if (!cur) cur = root;\n        if (cur_idx == s.size()) return cur->isWord && change == 1;\n        Node* next = cur->next[s[cur_idx] - \'a\'];\n        if (change == 1) {\n            if (!next) return false;\n            else return find(s, cur_idx + 1, 1, next);\n        } else {\n            if (next && find(s, cur_idx + 1, 0, next)) return true;\n            for (int i = 0; i < 26; i++) {\n                if (s[cur_idx] == \'a\' + i) continue;\n                if (cur->next[i] && find(s, cur_idx + 1, 1, cur->next[i])) return true;\n            }\n            return false;\n        }\n    }\n};\n\nclass MagicDictionary {\npublic:\n    /** Initialize your data structure here. */\n    MagicDictionary() {\n        trie = new Trie();\n    }\n    \n    /** Build a dictionary through a list of words */\n    void buildDict(vector<string> dict) {\n        for(string s: dict){\n            trie->insert(s);\n        }\n    }\n    \n    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */\n    bool search(string word) {\n        return trie->find(word, 0);\n    }\nprivate:\n    Trie* trie;\n};\n```\n
[]