Intuition Explained || Trie + Backtracking || C++ Clean Code
Intuition : \n\n Idea is to insert new word into Trie with addWord. Similar to insert function in Trie Implementation\n To search word we will search in similar
**Intuition :** \n\n* Idea is to insert new word into Trie with `addWord`. Similar to `insert` function in **[Trie Implementation](https://leetcode.com/problems/implement-trie-prefix-tree/)**\n* To `search` word we will search in similar was as done in standard Trie `search`. Catch here is the case when character in word is `.`\n* To handle this, we need to try all possible characters from `a to z` , by recusively doing checks. This is a backtracking based approach where we `pick -> try -> unpick` certains element. \n* And when we reach the end of the word, simply check if current Trie node has `isEnd` flag set as *True or False*\n\n# Code:\n\n```\nstruct Node {    // Trie Structure\n    Node* arr[26];\n    bool isEnd = false;\n    \n    bool contains(char ch) {\n        return arr[ch-\'a\'] != NULL;\n    }\n    \n    void put(char ch, Node* newNode) {\n        arr[ch-\'a\'] = newNode;\n    }\n    \n    Node* getNext(char ch) {\n        return arr[ch-\'a\'];\n    }\n    \n    void setEnd() {\n        isEnd = true;\n    }\n    \n    bool getEnd() {\n        return isEnd;\n    }\n    \n};\n\nclass WordDictionary {\n    Node* root;\npublic:\n    WordDictionary() {\n        root = new Node();\n    }\n    \n    void addWord(string word) {  // Insert word into Trie\n        Node* temp = root;\n        for(auto& ch : word) {\n            if(!temp->contains(ch)) {\n                temp->put(ch, new Node());\n            }\n            temp = temp->getNext(ch);\n        }\n        temp->setEnd();\n    }\n    \n    bool check(Node* node, string& word, int idx=0) {\n        if(!node) return false;\n        if(idx == word.size()) return node->getEnd();\n        \n        if(word[idx] == \'.\') {\n            for(char ch = \'a\'; ch <= \'z\'; ch++) {\n                if(!node->contains(ch)) continue;\n                if(check(node->getNext(ch), word, idx+1)) return true;\n            }\n        }\n        else if(node->contains(word[idx])) {\n             return check(node->getNext(word[idx]), word, idx+1);\n        }\n        \n        return false;\n    }\n    \n    bool search(string word) {\n        return check(root, word);\n    }\n};\n```\n\n***If you find this solution helpful, please do upvote :)***
['Backtracking', 'Depth-First Search', 'Trie', 'C']