Trie C++  - Easy To understand (124 ms)
We have used Trie to make the solution efficient as compared to bruteforce.\n2. The idea here is to create a TrieNode class which has 26 elements which are engl
1. We have used Trie to make the solution efficient as compared to bruteforce.\n2. The idea here is to create a TrieNode class which has 26 elements which are english alphabets and a flag variable which indicates if the string has come to an end.\n3. For the simplicity of the WordDictionary class we have included all the required function calls in the TrieNode Class.\n\nThe first word is the root and for adding more words we create a new Node and link it with previous. We make a comparison before creating a node for making sure that the word does not exist in the Trie.\nFor searching we created a helper function in which we pass the node which is linked to the current word.\nTo handle . in search we chck if our trie has any path available where the required output is possible.\n\n\n```\nclass TrieNode{\n    public:\n    TrieNode *links[26];\n    bool flag = false;\n    bool hasKey(char ch){\n        return (links[ch-\'a\'] != NULL);\n    }\n    void put(char ch, TrieNode *node){\n        links[ch - \'a\'] = node;\n    }\n    TrieNode *get(char ch){\n        return links[ch - \'a\'];\n    }\n    void flagSwitch(){\n        flag=true;\n    }\n    bool isEnd(){\n        return flag == true;\n    }\n};\n\nclass WordDictionary {\npublic:\n    TrieNode *root;\n    WordDictionary() {\n        root = new TrieNode();\n    }\n    \n    void addWord(string word) {\n        TrieNode *node  = root;\n        for(int i=0;i<word.length();i++){\n            if(!node->hasKey(word[i])){\n                node->put(word[i],new TrieNode());\n            }\n            node = node->get(word[i]);\n        }\n        node->flagSwitch();\n    }\n    bool helper(string word, TrieNode *node){\n        for(int i=0;i<word.length();i++){\n            if(word[i]==\'.\'){\n\t\t\t\t/*\n\t\t\t\t\tThis piece of code is the key to solve this problem \n\t\t\t\t\tso what this line basically do is it checks if our string has any possibilty \n\t\t\t\t\tfor any character between a to z where we get our desired results. \n\t\t\t\t\tSo we just make a recursive call to the same function for \n\t\t\t\t\tevery possible character at the place of "."!\n\t\t\t\t*/\n                for(char ch=\'a\';ch<=\'z\';ch++){\n                    if(node->hasKey(ch) && helper(word.substr(i+1),node->get(ch))) \n                        return true;\n                }\n                return false;\n            }\n            else{\n            if(!node->hasKey(word[i])){\n                return false;\n            }\n            node = node->get(word[i]);\n            }\n        }\n        if(node->isEnd()) {\n            return true; \n        }\n        return false;     \n    }\n    \n    bool search(string word) {\n        TrieNode *node  = root;\n        return helper(word,node);\n    }\n};\n ```
['Trie', 'C']