Sum of Prefix Scores of Strings

Leetcode Problem:

• Sum of Prefix Scores of Strings

Summary

• Given an array of strings, the problem requires finding the sum of scores of every non-empty prefix of each string
• The score of a string is the number of strings that it is a prefix of.

Approach

• A Trie data structure is used to store the given words
• Each node in the Trie represents a character in the word
• The score of each node is the number of words that it is a prefix of
• The insert function is used to insert words into the Trie, and the getScore function is used to calculate the score of a given word.

Complexity

• O(n * m * 26) where n is the number of words and m is the maximum length of a word
• This is because in the worst case, we need to traverse the Trie for each word and for each character in the word.

Explain

• The insert function is used to insert words into the Trie
• It starts from the root node and traverses the Trie based on the characters in the word
• The score of each node is incremented whenever a word is inserted
• The getScore function is used to calculate the score of a given word
• It starts from the root node and traverses the Trie based on the characters in the word, adding the score of each node to the total score.

Solution Code:

struct trie{
    int score;
    trie* next[26];
    bool tail;
    trie(){
        score = 0;
        for(int i = 0 ; i < 26; i++){
            next[i] = nullptr;
        }
        tail = false;
    }
    ~trie(){
        for(int i = 0 ; i < 26; i++){
            if(next[i] != nullptr) delete next[i];
            next[i] = nullptr;
        }
    }
};

void insert(trie* root, string &s, int s_idx, int size){
    if (s_idx == size) {
        root->tail = true;
        return;
    }
    int idx = s[s_idx]-'a';
    if(root->next[idx] == nullptr){
        root->next[idx] = new trie();
    }
    root->next[idx]->score++;
    insert(root->next[idx], s, s_idx+1, size);
}
int getScore(trie* root, string &s, int s_idx, int size){
    if(s_idx == size) return root->score;
    int idx = s[s_idx] - 'a';
    return root->score + getScore(root->next[idx], s, s_idx + 1, size);
}

class Solution {
public:
    vector sumPrefixScores(vector& words) {
        trie t;
        vector ans;
        for(string word : words){
            insert(&t, word, 0, word.size());
        }
        for(string word : words){
            int score = getScore(&t, word, 0, word.size());
            ans.push_back(score);
        }
        return ans;
    }
};