Sum of Prefix Scores of Strings

Problem Description

Welcome to the whimsical world of strings, where every character has a story to tell! The problem at hand, “Sum of Prefix Scores of Strings,” is like trying to figure out how many times your name gets called at a family reunion. Spoiler alert: it’s a lot!

Imagine you have a list of words, and you want to calculate the score for each word based on how many times its prefixes appear in the list. For instance, if your name is “Sam,” and the list includes “Sam,” “Samantha,” and “Sammy,” then the prefix “Sam” gets a score of 3. It’s like being the popular kid in school, but instead of friends, you have prefixes!

Code Solution


class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.count = 0

class Solution:
    def sumPrefixScores(self, words: list[str]) -> list[int]:
        root = TrieNode()

        def insert(word: str) -> None:
            node: TrieNode = root
            for c in word:
                node = node.children.setdefault(c, TrieNode())
                node.count += 1

        for word in words:
            insert(word)

        def getScore(word: str) -> int:
            node: TrieNode = root
            score = 0
            for c in word:
                node = node.children[c]
                score += node.count
            return score

        return [getScore(word) for word in words]

Approach Explanation

The code uses a Trie (prefix tree) to efficiently store and count the occurrences of each prefix. Here’s how it works:

Insert: For each word, we traverse through its characters, creating nodes in the Trie and incrementing the count for each character.
Get Score: For each word, we traverse the Trie again, summing up the counts of each prefix to get the total score.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of words and M is the maximum length of a word.
Space Complexity	O(N * M) as well, since we are storing all the characters of the words in the Trie.

Real-World Example

Think of it like a popularity contest at a party. Each name (word) gets points based on how many times it’s called out (prefixes). If “Sam” is called out three times, it’s the life of the party! Similarly, the algorithm counts how many times each prefix appears, giving us the score for each word.