Problem of The Day: Sum of Prefix Scores of Strings

Problem Statement

Intuition

The problem requires us to compute a score for each word based on the frequencies of its prefixes in the list of words. My first thought was to use a trie (prefix tree) structure, as it allows us to efficiently store and search for prefixes.

Approach

1. Building the Trie:
   • For each word in the list, add it to the trie while keeping track of the count of each prefix.
   • As we add each character of a word to the trie, we increment the count for that prefix. This count will represent how many times that particular prefix appears in the list of words.

2. Calculating Scores:

   • For each word, traverse through the trie again, summing up the counts of each character (prefix) encountered.
   • This sum will be the score for that word, as it represents the cumulative frequency of all its prefixes.
3. Result Compilation:
   • Store the calculated scores for each word in a result list and return it.

Complexity

• Time complexity:
  \(O(m \cdot n)\), where \(n\) is the number of words and \(m\) is the average length of the words. This accounts for building the trie and calculating the scores.

• Space complexity:
  \(O(m \cdot n)\), as we need to store each word in the trie and additional information (count) for each node.

Code

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        trie = {}
        for word in words:
            curr = trie
            for c in word:
                if c not in curr:
                    curr[c] = {'count': 0}
                curr[c]['count'] += 1
                curr = curr[c]

        res = []
        for word in words:
            curr = trie
            temp = 0
            for c in word:
                if c in curr:
                    temp += curr[c]['count']
                    curr = curr[c]
            res.append(temp)
        return res

Editorial

Approach: Tries

class trie_node:
    def __init__(self):
        self.next = [None] * 26
        self.cnt = 0


class Solution:
    def __init__(self):
        # Initialize the root node of the trie.
        self.root = trie_node()

    # Insert function for the word.
    def insert(self, word):
        node = self.root
        for c in word:
            # If new prefix, create a new trie node.
            if node.next[ord(c) - ord("a")] is None:
                node.next[ord(c) - ord("a")] = trie_node()
            # Increment the count of the current prefix.
            node.next[ord(c) - ord("a")].cnt += 1
            node = node.next[ord(c) - ord("a")]

    # Calculate the prefix count using this function.
    def count(self, s):
        node = self.root
        ans = 0
        # The ans would store the total sum of counts.
        for c in s:
            ans += node.next[ord(c) - ord("a")].cnt
            node = node.next[ord(c) - ord("a")]
        return ans

    def sumPrefixScores(self, words):
        N = len(words)
        # Insert words in trie.
        for i in range(N):
            self.insert(words[i])
        scores = [0] * N
        for i in range(N):
            # Get the count of all prefixes of given string.
            scores[i] = self.count(words[i])
        return scores

• time: O(N*M)
• space: O(N*M)