EASY  SOLUTION | | TRIE | |
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: The insert and search function are of O(length of word) time complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstruct Node{\n    Node* links[26];\n    bool flag;\n    public:\n    bool containsKey(char ch)\n    {\n        return links[ch-\'a\']!=NULL;\n    }\n    void put(char ch,Node* node)\n    {\n        links[ch-\'a\']=node;\n    }\n    Node* get(char ch)\n    {\n        return links[ch-\'a\'];\n    }\n    bool isEnd()\n    {\n        return flag;\n    }\n    void setEnd()\n    {\n        flag=true;\n    }\n};\nclass WordDictionary \n{\n    Node* root;\npublic:\n    WordDictionary() \n    {\n        root=new Node();\n    }\n    \n    void addWord(string word) \n    {\n        Node* node=root;\n        for(int i=0;i<word.size();i++)\n        {\n            if(!node->containsKey(word[i]))\n            {\n                node->put(word[i],new Node());\n            }\n            node=node->get(word[i]);\n        }\n        node->setEnd();\n    }\n    bool helper(Node* root,string word,int index)\n    {\n        if(index==word.size() && root->isEnd()==true)\n            return true;\n        if(index==word.size() && root->isEnd()==false)\n            return false;\n        if(word[index]==\'.\')\n        {\n            for(int i=0;i<26;i++)\n            {\n                bool a;\n                if(root->links[i]!=NULL)\n                    a=helper(root->links[i],word,index+1);\n                    if(a==true)             \n                    return true;\n            }\n            return false;\n        }\n        else\n        {\n            if(root->links[word[index]-\'a\']==NULL)\n            return false;\n            return helper(root->links[word[index]-\'a\'],word,index+1);\n        }\n    }\n    bool search(string word) \n    {\n        Node* node=root;\n        return helper(node,word,0);\n    }\n\n};\n\n/**\n * Your WordDictionary object will be instantiated and called as such:\n * WordDictionary* obj = new WordDictionary();\n * obj->addWord(word);\n * bool param_2 = obj->search(word);\n */\n```
['Trie', 'C++']