Sum of Prefix Scores of Strings || DCC 25/09/24 || Trie Solution ✅✅
Intuition\nThe problem revolves around finding the sum of scores for all prefixes of each word in the list. A Trie (prefix tree) is particularly suited for this
# Intuition\nThe problem revolves around finding the sum of scores for all prefixes of each word in the list. A Trie (prefix tree) is particularly suited for this task, as it efficiently stores and retrieves prefixes of words. By traversing the Trie, we can track how many times each prefix appears, which allows us to compute the score for each word\'s prefixes.\n\n# Approach\n**Trie Construction:**\n- We use a Trie where each node corresponds to a character, and cnt at each node stores the number of words that pass through that node (i.e., the number of words with a given prefix).\nInsert each word into the Trie. For every character of the word, we traverse the Trie, creating nodes as necessary and incrementing the cnt at each node to keep track of how many words have that prefix.\n\n**Score Calculation:**\n- For each word, we calculate the sum of scores of all its prefixes by traversing the Trie from the root for each prefix. At each node corresponding to a character, we add the cnt value (indicating how many words share this prefix) to the total score for that word.\n\n**Efficiency:**\n- The Trie allows us to efficiently find the score for each word\'s prefixes in linear time relative to the length of the word.\n\n**Code Explanation:**\n- The Trie class manages the Trie structure. It has methods:\n->insert: To add a word to the Trie.\n->search: To retrieve the count of words sharing a given prefix.\n- The sumPrefixScores function first inserts all the words into the Trie. Then for each word, it computes the total score by summing up the counts for each prefix in the Trie.\n\n# Complexity\n**Time complexity:**\n- Insertion: Inserting a word into the Trie takes $$O(L)$$ time where L is the length of the word. For n words with average length L, it takes $$O(n * L)$$ to insert all words.\n- Score Calculation: For each word, calculating the score involves traversing its prefixes, which also takes $$O(L)$$. For n words, this takes $$O(n * L)$$.\n- Overall time complexity is O(n * L), where n is the number of words, and L is the average length of the words.\n\n**Space complexity:**\n- The space complexity is $$O(n * L)$$ due to the Trie structure, which can have at most `n * L` nodes in the worst case (if all words are unique and share no common prefixes).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    class Trie {\n    public:\n        Trie() {\n            cnt = 0;\n            for(int i=0;i<26;i++){\n                this->next[i] = NULL;\n            }\n        }\n        void insert(string word, Trie* root) {\n            Trie* node = root;\n            int i = 0;\n            for (char ch : word) {\n                ch -= \'a\';\n                if (!node->next[ch]) { node->next[ch] = new Trie(); }\n                node->next[ch]->cnt++;\n                node = node->next[ch];\n                i++;\n            }\n        }\n\n        int search(char ch, Trie* node) {\n            return node->next[ch-\'a\']->cnt;\n        }\n\n        Trie* next[26] = {};\n        int cnt;\n    };\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie t;\n        Trie *root = new Trie();\n        int n = words.size();\n        for(int i=0;i<n;i++){\n            t.insert(words[i], root);\n        }\n        vector<int> ans;\n        for(int i=0;i<n;i++){\n            string cur = "";\n            int c = 0;\n            Trie *node = root;\n            for(int j=0;j<words[i].length();j++){\n                c += t.search(words[i][j], node);;\n                if(node->next[words[i][j]-\'a\'] == NULL) break;\n                node = node->next[words[i][j]-\'a\'];\n            }\n            ans.push_back(c);\n        }\n        return ans;\n    }\n};\n```
['Array', 'Trie', 'C++']