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.

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists of lowercase English letters.

Approach 01:

struct TrieNode {
    TrieNode* children[26] = {};  // Array of TrieNode pointers for 26 lowercase letters
    int prefixCount = 0;  // Keeps track of prefix count
};

class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        vector<int> prefixScores;
        TrieNode* root = new TrieNode();

        // Insert all words into the Trie
        for (const string& word : words) {
            insertWord(word, root);
        }

        // Calculate prefix scores for all words
        for (const string& word : words) {
            prefixScores.push_back(calculatePrefixScore(word, root));
        }

        // Clean up dynamically allocated Trie nodes
        deleteTrie(root);

        return prefixScores;
    }

private:
    // Inserts a word into the Trie
    void insertWord(const string& word, TrieNode* root) {
        TrieNode* currentNode = root;
        for (const char character : word) {
            int index = character - 'a';
            if (!currentNode->children[index]) {
                currentNode->children[index] = new TrieNode();
            }
            currentNode = currentNode->children[index];
            currentNode->prefixCount += 1;
        }
    }

    // Calculates the score for the given word based on the Trie
    int calculatePrefixScore(const string& word, TrieNode* root) {
        TrieNode* currentNode = root;
        int totalScore = 0;
        for (const char character : word) {
            currentNode = currentNode->children[character - 'a'];
            totalScore += currentNode->prefixCount;
        }
        return totalScore;
    }

    // Recursively delete all Trie nodes to free up memory
    void deleteTrie(TrieNode* node) {
        for (int i = 0; i < 26; ++i) {
            if (node->children[i]) {
                deleteTrie(node->children[i]);
            }
        }
        delete node;
    }
};

class TrieNode:
    def __init__(self):
        # Array of TrieNode pointers for 26 lowercase letters (a to z)
        self.children = [None] * 26
        # Keeps track of the prefix count
        self.prefixCount = 0


class Solution:
    def sumPrefixScores(self, words):
        prefixScores = []
        # Initialize the root of the Trie
        root = TrieNode()

        # Insert all words into the Trie
        for word in words:
            self.insertWord(word, root)

        # Calculate prefix scores for all words
        for word in words:
            prefixScores.append(self.calculatePrefixScore(word, root))

        return prefixScores

    # Inserts a word into the Trie
    def insertWord(self, word, root):
        currentNode = root
        for character in word:
            index = ord(character) - ord('a')
            if not currentNode.children[index]:
                currentNode.children[index] = TrieNode()
            currentNode = currentNode.children[index]
            currentNode.prefixCount += 1

    # Calculates the score for the given word based on the Trie
    def calculatePrefixScore(self, word, root):
        currentNode = root
        totalScore = 0
        for character in word:
            index = ord(character) - ord('a')
            currentNode = currentNode.children[index]
            totalScore += currentNode.prefixCount
        return totalScore

Time Complexity

• Trie Insertion:

  Inserting each word into the Trie takes \(O(L)\) time, where \(L\) is the length of the word. If there are \(n\) words and the average word length is \(m\), then inserting all words into the Trie takes \(O(n \times m)\) time.

• Prefix Score Calculation:

  For each word, calculating the prefix score also takes \(O(L)\), where \(L\) is the length of the word. Therefore, calculating prefix scores for all words takes \(O(n \times m)\) time.

• Cleaning Up the Trie:

  The recursive deletion of the Trie nodes visits each node exactly once. Since there are at most \(n \times m\) nodes in the Trie (one node for each character of each word), this operation takes \(O(n \times m)\) time.

• Overall Time Complexity:

  The overall time complexity is \(O(n \times m)\), where \(n\) is the number of words and \(m\) is the average length of the words.

Space Complexity

• Trie Storage:

  In the worst case, every character of every word needs a new Trie node, and there are \(26\) possible children for each node. So, the space required for the Trie is \(O(n \times m)\), where \(n\) is the number of words and \(m\) is the average length of the words.

• Auxiliary Space:

  We use additional space for storing the result (`prefixScores`), which takes \(O(n)\) space, where \(n\) is the number of words. The recursive `deleteTrie` function uses \(O(m)\) space for the recursion stack in the worst case, where \(m\) is the depth of the Trie (the maximum length of a word).

• Overall Space Complexity:

  The overall space complexity is \(O(n \times m)\) due to the Trie structure, with an additional \(O(n)\) for storing results.