2416. Sum of Prefix Scores of Strings

You are given an array words of size n consisting of non-empty strings.

We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].

• For example, if words = [“a”, “ab”, “abc”, “cab”], then the score of “ab” is 2, since “ab” is a prefix of both “ab” and “abc”.

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Note that a string is considered as a prefix of itself.

struct Trie {
    Trie* next[26];
    int count;
    Trie():count(0) {memset(next,0,sizeof next);}

    void insert(string& s, int p = 0) {
        count++;
        if(p == s.length()) return;
        else {
            if(!next[s[p]-'a']) next[s[p]-'a'] = new Trie();
            next[s[p]-'a']->insert(s,p + 1);
        }
    }

    int query(string s, int p = 0) {
        if(p == s.length()) return count;
        else {
            return count + next[s[p]-'a']->query(s,p+1);
        }
    }
};
class Solution {
    Trie* trie;
    int query(string s) {
        int res = 0;
        Trie* runner = trie;
        for(int i = 0; i < s.length(); i++) {
            res += runner->count;
            runner = runner->next[s[i]-'a'];
        }
        return res + runner->count;
    }
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        trie = new Trie();
        for(auto& w : words) trie->insert(w);
        vector<int> res;
        for(auto& w : words) res.push_back(query(w) - words.size());
        return res;

    }
};