C++ | Trie | Easy to Understand
Intuition\nIt would be better to first understand Implement Trie (Explanation) before attempting this problem. \n\nHere we will be using trie to store the words
# Intuition\nIt would be better to first understand [Implement Trie (Explanation)](https://leetcode.com/problems/implement-trie-prefix-tree/solutions/3306611/explained-with-example-easy-to-understand/) before attempting this problem. \n\nHere we will be using trie to store the words. Each node in the Trie represents a character, and the path from the root node to a particular node represents a string or word. The end of a word is marked by a flag in the last node of the word.\n\nTo search, if we encounter a \'.\', then we would skip that character and recursively search for the remaining characters. Else we would check whether the current alphabet exists or not. If not return false, else call recursion on remaining characters.\n\n\n# Code\n```\nstruct TrieNode {\n    bool end; // Flag to indicate whether this node represents the end of a word or not\n    vector<TrieNode*>children=vector<TrieNode*>(26,nullptr); // Vector of pointers to child nodes for each possible character in the alphabet (26 lowercase English letters)\n};\n\nclass WordDictionary {\npublic:\n    TrieNode* root;\n    WordDictionary() {\n        root=new TrieNode();\n    }\n    \n    // Insert a word into the Trie\n    void addWord(string word) {\n        TrieNode* curr=root;\n        for(char c:word){\n            int index=c-\'a\';\n            if(!curr->children[index]){\n                curr->children[index]=new TrieNode();\n            }\n            curr=curr->children[index];\n        }\n        curr->end=true; // Mark the last node as the end of the word\n    }\n\n    // Search for a word in the Trie\n    bool pathSearch(string word, TrieNode* root, int index){\n        if(index==word.size()) return root->end; // return true if the last node is marked as the end of a word\n        TrieNode* node=root;\n        char c=word[index];\n        int idx=c-\'a\';\n        if(c==\'.\'){   // if character is \'.\' check for remaining characters in all nodes\n            for(int i=0;i<26;i++){\n                if(node->children[i]){\n                   bool search= pathSearch(word,node->children[i],index+1); \n                   if(search) return true;\n                }\n            }\n            return false;\n        }\n        else{\n            if(!node->children[idx])return false; // if the current character doesn\'t exist return false\n            return pathSearch(word,node->children[idx],index+1); // if current character exists check for remaining characters\n        }\n    }\n    \n    bool search(string word) {\n        return pathSearch(word,root,0);\n    }\n};\n\n```
['C++']