##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2416.html

# 2416. Sum of Prefix Scores of Strings

• Difficulty: Hard.
• Related Topics: .
• Similar Questions: Design Add and Search Words Data Structure, Maximum XOR of Two Numbers in an Array, Map Sum Pairs.

## Problem

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.

## Solution (Java, C++, Python)

• class Trie {
Trie[] ch = new Trie[26];
int visited = 0;
}
class Solution {
public int[] sumPrefixScores(String[] words) {
Trie trie = new Trie();
int[] ans = new int[words.length];
int k = 0;
for (String x: words) {
Trie t = trie;
for (int i = 0; i < x.length(); i++) {
int c = x.charAt(i) - 'a';
if (t.ch[c] == null) t.ch[c] = new Trie();
t.ch[c].visited++;
t = t.ch[c];
}
}
for (String x: words) {
Trie t = trie; int curr = 0;
for (int i = 0; i < x.length(); i++) {
int c = x.charAt(i) - 'a';
curr += t.ch[c].visited;
t = t.ch[c];
}
ans[k++] = curr;
}
return ans;
}
}

• class Trie:
def __init__(self):
self.children = [None] * 26
self.cnt = 0

def insert(self, w):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.cnt += 1

def search(self, w):
node = self
ans = 0
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return ans
node = node.children[idx]
ans += node.cnt
return ans

class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
trie = Trie()
for w in words:
trie.insert(w)
return [trie.search(w) for w in words]

############

# 2416. Sum of Prefix Scores of Strings
# https://leetcode.com/problems/sum-of-prefix-scores-of-strings

class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
N = len(words)
res = [0] * N
mp = defaultdict(int)

for word in words:
prefix = ""

for char in word:
prefix += char
mp[prefix] += 1

for index, word in enumerate(words):
prefix = ""
count = 0

for char in word:
prefix += char
count += mp[prefix]

res[index] = count

return res


• class Trie {
private:
vector<Trie*> children;
int cnt;

public:
Trie()
: children(26)
, cnt(0) {}

void insert(string& w) {
Trie* node = this;
for (char c : w) {
int idx = c - 'a';
if (!node->children[idx]) node->children[idx] = new Trie();
node = node->children[idx];
++node->cnt;
}
}

int search(string& w) {
Trie* node = this;
int ans = 0;
for (char c : w) {
int idx = c - 'a';
if (!node->children[idx]) return ans;
node = node->children[idx];
ans += node->cnt;
}
return ans;
}
};

class Solution {
public:
vector<int> sumPrefixScores(vector<string>& words) {
Trie* trie = new Trie();
for (auto& w : words) {
trie->insert(w);
}
vector<int> ans;
for (auto& w : words) {
ans.push_back(trie->search(w));
}
return ans;
}
};

• type Trie struct {
children [26]*Trie
cnt      int
}

func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(w string) {
node := this
for _, c := range w {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
node.cnt++
}
}

func (this *Trie) search(word string) int {
node := this
ans := 0
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
return ans
}
node = node.children[c]
ans += node.cnt
}
return ans
}

func sumPrefixScores(words []string) []int {
trie := newTrie()
for _, w := range words {
trie.insert(w)
}
ans := make([]int, len(words))
for i, w := range words {
ans[i] = trie.search(w)
}
return ans
}

• class Trie {
children: Array<any>;
cnt: number;

constructor() {
this.children = Array(26);
this.cnt = 0;
}

insert(w: string): void {
let node = this;
for (const c of w) {
const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!node.children[idx]) {
node.children[idx] = new Trie();
}
node = node.children[idx];
node.cnt++;
}
}

search(w: string): number {
let node = this;
let ans = 0;
for (const c of w) {
const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (!node.children[idx]) {
return ans;
}
node = node.children[idx];
ans += node.cnt;
}
return ans;
}
}

function sumPrefixScores(words: string[]): number[] {
const trie = new Trie();
for (const w of words) {
trie.insert(w);
}
let ans = [];
for (const w of words) {
ans.push(trie.search(w));
}
return ans;
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).