trie| c++ 🔥 the very fundamental of trie data structure Easy & Intutive
first of all how we can identify that this problem is related to trie data structure?\n\n\ntime complexcity total: Sum (size of each words)<=10^6\nspace complex
first of all how we can identify that this problem is related to trie data structure?\n\n```\ntime complexcity total: Sum (size of each words)<=10^6\nspace complexcity total : Sum (size of each words) <=10^6\n```\n\nfirst when we see what they are asking is calculate sum of ( frequencies of prefixes  (prifix which is genrated by given string)  ) in entire set of string\nthis can be very ambigeous to think but let me clear it :\n```\nlet\'s say we have two string only for simplicity : "abc", "ab"\n```\n\n```\nso count of prifix:\n"a" = 2    one a is genrated by abc and other is genrated by ab\n"ab" = 2   one ab is genrated by abc and other is genrated by ab\n"abc" = 1  abc can be genrated by abc only\n```\n\n```\nso now when we take abc :\nwe have 3 possible prifixes: {"a", "ab",  "abc"}\n```\n```\nnow we look into our globle frequency list and sum it which will be the answer for abc:\n2 a + 2 ab + 1 abc= 5\nsimilarly for ab\n2 a + 2 ab = 4\n```\n\nso what we are summing here?\nbasically the count of common path followed by each string, path mean common prifixes which are present in each string\n\n\nremeber how we store each string in trie?\nfor each character we create a node thus it form a tree and we can say that a word follows the path of it\'s char\'s node to the end \nbut on key thing to notice here is we want to calculate the frequency of each prefixes so we don\'t need to mark end of the word but here strating from first char where ever u stop that\'s one of your prefixes so here we will keep count at nodes how many words have passed this node \n\nand once we created the entire tree we will just collect all sum by traversing from root for each word\n\n```\n\nclass Solution {\npublic:\n    \n    class trie\n    {\n        public:\n        trie* next[26];\n        int end;\n\n        trie()\n        {\n            for(int i=0; i<26; i++)\n            next[i]=NULL;\n            end=0;\n        }\n\n    };\n\t\n\t//build the tree\n    trie* maketree(vector<string> &s)\n    {\n        trie* root=new trie();\n        for(int i=0; i<s.size(); i++)\n        {\n            trie* curr=root;\n            for(int j=0; j<s[i].size(); j++)\n            {\n               if(curr->next[s[i][j]-\'a\']==NULL)\n               {\n                   curr->next[s[i][j]-\'a\']=new trie();\n                   \n               }\n                curr=curr->next[s[i][j]-\'a\'];\n                curr->end+=1;  // increment by one when ever any word passes this node\n                   \n            }\n            \n        }\n        \n        return root;\n        \n        \n    }\n    \n    \n    int sum(string &s, trie* &root)\n    {\n        trie* curr= root;\n        int ans=0;\n        int n=s.size();\n        for(int i=0; i<n; i++)\n        {\n            curr= curr->next[s[i]-\'a\'];\n            ans+= curr->end; // accumulate all the sum while moving down with each word\n        }\n        return ans;\n        \n    }\n    \n    vector<int> sumPrefixScores(vector<string>& words) \n    {\n        trie* root= maketree(words);\n        vector<int> ans;\n        for(auto i: words)\n        {\n            ans.push_back(sum(i,root));\n        }\n        return ans;\n    }\n};\n\n\n\n```\n\n\n\n\n\n
['Trie', 'C']