#2416

Hard

LeetCode Problem Workspace

Sum of Prefix Scores of Strings

The 'Sum of Prefix Scores of Strings' problem involves calculating prefix scores for strings based on their occurrences as prefixes.

array string trie counting

Problem Statement

You are given an array of non-empty strings called words, where each word is a string made of lowercase English letters.

For each word in the array, compute the sum of scores for all of its non-empty prefixes. The score of a prefix is the number of strings in words that have this prefix.

Examples

Example 1

Input: words = ["abc","ab","bc","b"]

Output: [5,4,3,2]

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.

Example 2

Input: words = ["abcd"]

Output: [4]

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

Constraints

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists of lowercase English letters.

Solution Approach

Trie Construction

The key to solving this problem efficiently is using a trie (prefix tree). Insert each string into the trie and maintain a count of how many times a prefix appears. This allows us to quickly look up the number of words that contain any given prefix.

Prefix Score Calculation

Once the trie is built, iterate through each word and compute the score for every non-empty prefix by summing the counts from the trie. For each word, start from the root of the trie and traverse down for each prefix, adding the count at each step to get the total score.

Efficient Score Summation

To optimize the solution, make sure to reuse the prefix scores already computed for earlier prefixes in each word. This minimizes redundant calculations, reducing overall complexity.

Complexity Analysis

Metric	Value
Time	O(N \cdot M)
Space	O(N \cdot M)

The time complexity of this solution is O(N * M), where N is the number of words and M is the maximum length of a word. This accounts for inserting each word into the trie and calculating scores for each prefix. The space complexity is O(N * M) due to the trie storing all words and their prefixes.

What Interviewers Usually Probe

The candidate should be able to recognize the importance of trie data structures in solving this problem efficiently.
Look for an explanation of how the trie helps track prefix counts, and ensure the candidate understands how it avoids redundant calculations.
The candidate should demonstrate an understanding of both array manipulation and string handling while solving this problem.

Common Pitfalls or Variants

Common pitfalls

Not using a trie can lead to inefficient solutions that directly compare prefixes for each word, leading to high time complexity.
Failing to reuse previously computed prefix scores for efficiency, resulting in redundant work and unnecessary complexity.
Not properly handling edge cases where a word has very few or very long prefixes.

Follow-up variants

Modify the problem to only calculate prefix scores for specific prefixes of each word.
Extend the problem to allow for case-sensitive strings or strings with non-alphabetic characters.
Alter the problem to ask for the number of words with each exact prefix rather than the sum of prefix scores.

FAQ

How do I handle large strings and arrays in the 'Sum of Prefix Scores of Strings' problem?

Use a trie to efficiently track prefix counts, which allows the solution to handle large inputs without excessive redundancy in calculations.

What data structure is most efficient for solving the 'Sum of Prefix Scores of Strings' problem?

A trie is the most efficient data structure for solving this problem as it allows for quick lookup of prefix counts while inserting strings.

Why is a brute-force solution not ideal for the 'Sum of Prefix Scores of Strings' problem?

A brute-force approach that checks all prefixes for every word leads to high time complexity. A trie reduces this by efficiently counting prefix occurrences.

What is the time complexity of the 'Sum of Prefix Scores of Strings' problem?

The time complexity is O(N * M), where N is the number of words and M is the length of the longest word.

How do I optimize memory usage in the 'Sum of Prefix Scores of Strings' problem?

By using a trie, you can optimize memory usage since the trie stores only necessary prefixes, making it more space-efficient than alternative solutions.

terminal

Solution

Solution 1: Prefix Tree

We can use a prefix tree to maintain all prefixes of the strings and count the occurrences of each prefix.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

class Trie:
    __slots__ = "children", "cnt"

    def __init__(self):
        self.children = [None] * 26
        self.cnt = 0

    def insert(self, w):
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            node.cnt += 1

    def search(self, w):
        node = self
        ans = 0
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                return ans
            node = node.children[idx]
            ans += node.cnt
        return ans


class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        trie = Trie()
        for w in words:
            trie.insert(w)
        return [trie.search(w) for w in words]

Continue Practicing

#2452 words within two edits of dictionary #2506 count pairs of similar strings #2284 sender with largest word count