# Sum of Prefix Scores of Strings

Published: Dec 26, 2022

Hard Trie Counting String

## Problem Description

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.

Constraints:

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

https://leetcode.com/problems/sum-of-prefix-scores-of-strings/

## Examples

``````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 = 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 = 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 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer = 2.
``````
``````Example 2
Input: words = ["abcd"]
Output: 
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer = 1 + 1 + 1 + 1 = 4.
``````

## How to Solve

This is the Trie data structure problem. The problem asks duplicated characters of traversing all words. For example, when the two words are “abc” and “ab,” a -> b -> c and a -> b are traversed. While building a trie from given words, count up each character in each level. Once the trie creation is completed, traverse the given words exactly the same as the trie is built. Summing up each character’s count to the last character will give us an answer.

## Solution

``````struct TrieNode {
TrieNode *children;
int count = 0;
};

class SumOfPrefixScoresOfStrings {
private:
TrieNode *root = new TrieNode();

public:
vector<int> sumPrefixScores(vector<string>& words) {
TrieNode *root = new TrieNode();
for (string word : words) {
TrieNode *cur = root;
for (char c : word) {
if (!cur->children[c - 'a']) {
cur->children[c - 'a'] = new TrieNode();
}
cur = cur->children[c - 'a'];
cur->count++;
}
}
for (string word : words) {
TrieNode *cur = root;
int score = 0;
for (char c : word) {
cur = cur->children[c - 'a'];
score += cur->count;
}
}
}
};
``````
``````
``````
``````
``````
``````class TrieNode:
def __init__(self):
self.children = defaultdict(TrieNode)
self.count = 0

class SumOfPrefixScoresOfStrings:
def sumPrefixScores(self, words: List[str]) -> List[int]:
root = TrieNode()
for word in words:
cur = root
for c in word:
cur = cur.children[c]
cur.count += 1
for word in words:
cur = root
score = 0
for c in word:
cur = cur.children[c]
score += cur.count
``````
• Time: `O(m * n)` – m: number of words, n: length of each word (average)
• Space: `O(m * n)`