C++ Explained Solution | Using Trie | Time - O(NM) |
Approach -\nStep 1 - Create a node class that stores characters, a pointer to its next characters \nand count how many times this character appears in every pre
**Approach -**\n**Step 1** - Create a node class that stores characters, a pointer to its next characters \nand count how many times this character appears in every prefix of every string of a given vector\n**Step 2** - Create a trie class that has to member function\ni) Push - To push the string in trie\nii) Score - To find the score of the string :-\nCalculate the sum of the count of every character of string in trie\n**Step 3** - Push all strings of the given vector in trie\n**Step 4** - Get the score of every string of vector by calling the score function of trie\n\n**Code**\n```\nclass node{\n    public :\n    char c;\n    unordered_map<char,node*> m; // To store pointer to its next characters\n    int cn =0 ;  // To store count how many times this character appears in every prefix of every string of a given vector\n};\n\nclass trie{\n    node *r;  // Root node\n    public :\n    trie(){\n        r = new node;\n        r->c = \'\\0\';\n        r->cn = 0;\n    }\n    void push(string a){\n        node *p = r;\n        for(int i=0;i<a.size();i++){\n            if(p->m.count(a[i])){     // If its next character is present in trie, move to that character\n                p = p->m[a[i]];\n                p->cn++;              // Increase count, Because it is present in prefix of current string(a)\n            }\n            else{\n                node *l = new node;  // If its next character is not present in trie, create new node\n                l->c = a[i];\n                l->cn = 1;           // Count = 1\n                p->m[a[i]]= l;\n                p = l;\n            }\n        }\n        return ;\n    }\n    int score(string a){\n        int ans =0 ;\n        node *p = r;\n        for(int i=0;i<a.size();i++){    // Add all count of character by traversing trie for current string(a)\n            p= p->m[a[i]];\n            ans += p->cn;           \n        }\n        return ans;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> sumPrefixScores(vector<string>& a) {\n        trie t;\n        int n = a.size();\n        for(int i=0;i<n;i++) t.push(a[i]);              // Push all string in trie\n        vector<int> ans(n);\n        for(int i=0;i<n;i++) ans[i]= t.score(a[i]);    //  Get the score of strings\n        return ans;\n    }\n};\n```\n\n**Time Complexity - O(NM)**  => O(C)\nN is the length of the given array\nM is the length of the string (This may not be the same for all strings)\nC is the number of characters present in the given vector\n\n**Upvote if you like it!**\n
[]