Solving using TRIE concept || C++ 🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nIn simpler words, here\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIn simpler words, here\'s what you\'re doing in the code:\n\n### The Problem:\nYou have a list of words, and you want to see how many of them only use characters from a given set of "allowed" characters.\n\n### Solution with a Trie:\nTo solve that, you\'re creating a special data structure, called a **Trie**, which allows you to quickly determine whether a character is part of the allowed set.\n\nStep-by-Step Explanation\nStep 1: **Construct Trie**\n   Take the characters from the string `allowed` and shove them into the Trie. Think of the Trie as a tree in which each branch is just a letter. Whenever a character is allowed, you add it to the tree.\n- This means when you want to check whether a character is allowed at some later point, you can do that very fast.\n\n2. **Checking Words**:\n   - For each word in your list:\n     You go through every character of the word to see if it appears in the Trie, i.e., in the allowed characters.\n- All characters of the word are found in the Trie, and therefore the word is "consistent," meaning it only uses allowed characters.\n- Even one character of the word is not found in the Trie and therefore passes over as containing disallowed characters.\n\n3. **Efficiency**:\n- The Trie allows you to look up characters in constant time so looking up each character against the accepted string is much much faster than doing it manually.\n   - In this way, you can iterate through the list of words and quickly tally how many are in agreement with the accepted set.\n\n### Why Use a Trie?\nA Trie helps you store and check permitted characters very efficiently. Instead of looping over the permitted string for each word-by-word checking (which could be slow for large inputs), just build the Trie once and check characters in words almost instantly, making your solution faster and more scalable for bigger datasets.\n\nEssentially, it makes the checking process much faster by translating the allowed characters into a searchable structure with the help of the Trie. This helps count consistent words pretty efficiently.\n\n# Complexity\n- Time complexity:O(n*m) where n = length of words, m = avg length of word present in words. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(26)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass TrieNode {\npublic:\nTrieNode *children[26];\n\nTrieNode(){\n    for(int i = 0;i<26;i++)\n      {\n        children[i]=nullptr;\n      }\n  }\n};\n\nclass Trie\n{\n    public:\n    TrieNode* root;\n    Trie()\n    {\n       root = new TrieNode();\n    }\n\n    void insert(char c)\n    {\n        int index = c-\'a\';\n        if(root->children[index]==nullptr)\n        {\n            root->children[index]=new TrieNode();\n        }\n    }\n\n    bool containChar(char c)\n    {\n        if(root->children[c-\'a\']!=nullptr)return true;\n        return false;\n    }\n};\n\n\n\nclass Solution {\npublic:\n    int countConsistentStrings(string allowed, vector<string>& words) {\n        \n        Trie* trie = new Trie();\n        for(char &c:allowed)\n        {\n            trie->insert(c);\n        }\n        \n        int consistent = 0;\n        for(auto &str:words)\n        {    bool isconsistent = true;\n            for(int i=0;i<str.size();i++)\n            {\n                if(!trie->containChar(str[i]))\n                {\n                    isconsistent = false;\n                    break;\n                }\n            }\n            if(isconsistent)\n            {\n                consistent++;\n            }\n        }\n        \n        return consistent;\n    }\n};\n```
['Trie', 'C++']