"""
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.

hint:
1 What data structure will allow you to efficiently keep track of the score of each prefix?
2 Use a Trie. Insert all the words into it, and keep a counter at each node that will tell you how many times we have visited each prefix.

analysis:
TC O(n * m) n is numbers of words, m is the avg length of single word
"""
import collections
from typing import List

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.cnt = 0

class SumOfPrefixScoresOfStrings:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        root, res = TrieNode(), []
        for word in words:
            cur = root
            for c in word:
                i = ord(c) - ord('a')
                if i not in cur.children:
                    cur.children[i] = TrieNode()
                cur.children[i].cnt += 1
                cur = cur.children[i]
        for word in words:
            cur, score = root, 0
            for c in word:
                i = ord(c) - ord('a')
                score += cur.children[i].cnt
                cur = cur.children[i]
            res.append(score)
        return res
