sum of prefix scores of strings

25 September 2024
Leetcode,
RC

problem #

You are given an array words of size n consisting of non-empty strings.

We define the score of a string term as the number of strings words[i] such that term 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.

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]

Explanation

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

original solution #

for every term in words:
- count up to its total length
- make a prefix by slicing at that index
- store the prefix, and also count its frequency
reduce each term's list of prefixes to the sum of their frequencies

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        all_prefixes = []
        prefix_freqencies = {}

        for term in words:
            prefixes = []

            for i in range(len(term)):
                prefix = term[: i + 1]

                prefixes.append(prefix)

                if prefix in prefix_freqencies:
                    prefix_freqencies[prefix] += 1
                else:
                    prefix_freqencies[prefix] = 1

            all_prefixes.append(prefixes)

        res = []
        for prefixes in all_prefixes:
            total = 0
            for prefix in prefixes:
                total += prefix_freqencies[prefix]

            res.append(total)

        return res

Yesterday's hard stumped me, got this one first try. Motivating.

However, my solution is 30th percentile in speed: very slow.

fixed solution #

source

Use a trie.

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        # Build the trie structure from the list of words
        trie = self.buildTrie(words)
        # Calculate and return the prefix scores for each word
        return self.calculatePrefixScores(trie, words)

    def buildTrie(self, words: List[str]) -> Dict:
        trie = {}
        for word in words:
            node = trie
            for char in word:
                # Navigate through or create nodes in the trie
                node = node.setdefault(char, {})
                # Count occurrences of the prefix
                node["$"] = node.get("$", 0) + 1
        return trie

    def calculatePrefixScores(self, trie: Dict, words: List[str]) -> List[int]:
        scores = []
        for word in words:
            node = trie
            total_score = 0
            for char in word:
                # Move to the next node and accumulate the score
                node = node[char]
                total_score += node["$"]
            scores.append(total_score)
        return scores

the trie #

A trie stores any number of words by building up a tree of prefixes, starting with an empty root node.

The word "fast" would become the tree '' -> f -> fa -> fas -> fast.

The words "fast", "fall", and "of" would become the tree

   -> o -> of
'' -> f -> fa -> fas -> fast
              -> fal -> fall

In retrospect, their relationship to this question is obvious.

They also power autocompletion, spell check, and edit distance.

Previous: maximum number of non-overlapping substrings
Next: rank transform of an array