✅ Trie vs Brute-Force vs find()
Trie Method:\n\n1. First put all the words in the trie and keep on incrementing counting of prefix after every letter.\n2. Now traverse prefix and get the count
**Trie Method**:\n\n1. First put all the words in the trie and keep on incrementing counting of prefix after every letter.\n2. Now traverse prefix and get the count , number of word this prefix has occured.\n\n**It is a Standard Trie Implementation ALgorithm**\n**C++**\n  \n    struct Node{\n      Node* links[26];\n      int prefix=0;\n        \n      bool contains(char c){\n         return links[c-\'a\']!=0;\n      }    \n    \n      void create(char c,Node* node){\n          links[c-\'a\']=node;\n      }\n    \n      void increment(){\n          prefix++;\n      }\n    \n      int count(){\n          return prefix;\n      }\n    \n      Node* next(char c){\n          return links[c-\'a\'];\n      }\n    };\n\t\n\t//Trie Class\n    class Trie{\n      Node* root; \n      public:\n   \n      Trie(){\n          root=new Node();\n      }\n\t  \n      //insert words\n      void insert(string word){\n          Node* ptr=root;\n          for(auto i:word){\n             if(!ptr->contains(i))  ptr->create(i,new Node());\n             ptr=ptr->next(i);\n             ptr->increment();\n          }\n      }\n\t  \n      //return count of given prefix\n      int cnt_pref(string word){\n          Node* ptr=root;\n          for(auto i:word){\n              if(!ptr->contains(i)) return 0;\n              ptr=ptr->next(i);\n          }\n          return ptr->count();\n      }\n    };\n\t\n\t//input class\n\tclass Solution {\n    public:\n    int prefixCount(vector<string>& words, string pref) {\n        Trie trie;\n        for(auto i:words) trie.insert(i);  //no. of words*average length of strings\n        int cnt= trie.cnt_pref(pref);  //length of prefix\n        return cnt;\n    }\n    };\n**Time** - O(number of words * average length of words + prefix_length)\n**Space** - O(Average length * 26)\n\n# Find() Algorithm Method:\n   \n   \n    int prefixCount(vector<string>& words, string &pref) {\n        int cnt=0;\n        for(auto i:words){\n            auto q= i.find(pref);\n            if(q!=string::npos and q==0) cnt++;\n        }\n        return cnt;\n    }\n**Time** - O(N * M)\n**Space** - O(1)\n\t\n# Brute Force\t\n\n     bool check(string &x,string &y,int i){\n\t        if(i==y.size()) return true;\n            return x[i]==y[i]? check(x,y,i+1) : false;\n\t }\n\t \n     int prefixCount(vector<string>& words, string &pref){\n        int cnt=0;\n        for(auto i:words){\n            if(i.size()<pref.size()) continue;\n            cnt+= check(i,pref,0)? 1 : 0 ;\n        }\n        return cnt;\n    }\n**Time** - O(N * min(pref.size(),average length of strings)\n**Space** - O(1)\n
['C']