[C++] Trie solution with complexity analysis
\nclass MagicDictionary {\nprivate:\n    struct Trie {\n    private:\n        bool isEnd = false;\n        Trie *children[26];\n    public:\n        Trie () {\n
```\nclass MagicDictionary {\nprivate:\n    struct Trie {\n    private:\n        bool isEnd = false;\n        Trie *children[26];\n    public:\n        Trie () {\n            for (int i = 0; i < 26; i++) {\n                children[i] = NULL;\n            }\n        }\n        \n        void insert(string &s) {\n            Trie *curr = this;\n            for (char &c : s) {\n                int cVal = c - \'a\';\n                if (curr->children[cVal] == NULL) {\n                    curr->children[cVal] = new Trie();\n                }\n                curr = curr->children[cVal];\n            }\n            curr->isEnd = true;\n        }\n        \n        bool magicSearch(Trie *curr, string &s, int i, int diff) {\n            if (diff < 0) return false;\n            if (i == s.size()) return (curr->isEnd && diff == 0);\n            for (int j = 0; j < 26; j++) {\n                if (curr->children[j] == NULL) continue;\n                if (magicSearch(curr->children[j], s, i + 1, diff - (s[i] != \'a\' + j))) {\n                    return true;\n                }\n            }\n            return false;\n        }\n    };\n    Trie trie;\n    \npublic:\n    MagicDictionary() {\n        \n    }\n    \n\t// Time complexity: O(MN), M = dictionary size, N = string size\n\t// Space complexity: O(MN), becuase the worse case is that we have to store every character in trie\n    void buildDict(vector<string> dictionary) {\n        for (string &s : dictionary) {\n            trie.insert(s);\n        }\n    }\n    \n\t// Time complexity: O(MN), because the worse case is that we have to search each character in trie\n\t// Space complexity: O(N), due to recursion, in the worse case we will have a stack size poportional to the longest word\n    bool search(string searchWord) {\n        return trie.magicSearch(&trie, searchWord, 0, 1);\n    }\n};\n```
['Backtracking', 'Trie', 'C', 'C++']