Sum of Prefix Scores of Strings

lcpy gen -n 2416   # by problem number
lcpy gen -s sum_of_prefix_scores_of_strings   # by problem name

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.

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.

class Solution:
    # Time: O(total characters across all words)
    # Space: O(total characters) for the trie
    def sum_prefix_scores(self, words: list[str]) -> list[int]:
        children: list[dict[str, int]] = [{}]
        counts: list[int] = [0]

        for word in words:
            node = 0
            for ch in word:
                nxt = children[node].get(ch)
                if nxt is None:
                    nxt = len(children)
                    children[node][ch] = nxt
                    children.append({})
                    counts.append(0)
                node = nxt
                counts[node] += 1

        answer: list[int] = []
        for word in words:
            node = 0
            total = 0
            for ch in word:
                node = children[node][ch]
                total += counts[node]
            answer.append(total)
        return answer