Sum of Prefix Scores of Strings — Trie Count

Problem

For each word in words, compute the sum of scores of all its prefixes, where score of a prefix = number of words sharing that prefix.

Approach — Trie with count

At each trie node, store count = number of words passing through. For each word, traverse and sum counts.

Time: O(n * L) | Space: O(n * L)

Solutions

Python

class Solution:
    def sumPrefixScores(self, words: list[str]) -> list[int]:
        root={}
        for w in words:
            node=root
            for c in w:
                if c not in node: node[c]={'cnt':0}
                node=node[c]; node['cnt']+=1
        res=[]
        for w in words:
            node=root; score=0
            for c in w:
                node=node[c]; score+=node['cnt']
            res.append(score)
        return res

Complexity

Time: O(n * L) | Space: O(n * L)