Problem

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

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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: 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:

1
2
3
4
5

Input: words = ["abcd"]
Output: [4]
Explanation:
"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.

Solution

Method 1 - Using Hashmap

To solve this problem, we can follow these steps:

  1. Understand the Prefix Definition: A prefix of a word is any leading segment of the word, including the word itself.
  2. Prefix Scoring: For each word in the list, we need to check all possible prefixes of this word and count how many words in the given list start with these prefixes.
  3. Sum of Scores: For each word, compute the sum of scores for all its prefixes.

Here’s a plan for the implementation:

  1. Generate all prefixes for each word.
  2. Maintain a dictionary to count occurrences of each prefix in the list.
  3. Use the counts to compute the score for each word according to the rules.

Code

 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

class Solution {
    public int[] sumPrefixScores(String[] words) {
        // Create a map to store the count of each prefix
        Map<String, Integer> prefixCount = new HashMap<>();

        // Populate the map with prefix counts
        for (String word : words) {
            for (int j = 1; j <= word.length(); j++) {
                String prefix = word.substring(0, j);
                prefixCount.put(
                    prefix, prefixCount.getOrDefault(prefix, 0) + 1);
            }
        }

        // Create an array to store the result
        int[] result = new int[words.length];

        // Calculate the result for each word
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int score = 0;
            for (int j = 1; j <= word.length(); j++) {
                String prefix = word.substring(0, j);
                score += prefixCount.get(prefix);
            }
            result[i] = score;
        }

        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        from collections import defaultdict

        # Create a dictionary to store score of each prefix
        prefix_count = defaultdict(int)

        # Populate the dictionary with prefix counts
        for word in words:
            for j in range(1, len(word) + 1):
                prefix_count[word[:j]] += 1

        # Now we need to calculate the answer for each word
        result = []
        for word in words:
            score = 0
            for j in range(1, len(word) + 1):
                score += prefix_count[word[:j]]
            result.append(score)

        return result

Complexity

  • ⏰ Time complexity: O(m*n)
    • Calculating Prefix Counts: For each word of average length m, generating all prefixes takes O(m) time. Doing this for n words results in O(n \times m).
    • Calculating Scores: For each word, adding up the counts of its prefixes also takes O(m) time. Thus, for n words, this also results in O(n \times m).
    • Therefore, the overall time complexity is O(n \times m).
  • 🧺 Space complexity: O(n + m^2)
    • Prefix Count Map/Dictionary: In the worst case, every prefix of every word is unique. The number of such prefixes is (\sum_{i=1}^{m} n \times i = O(n \times m^2)). This is less common, and typical cases may have fewer prefixes.
    • Result Array: This requires O(n) space.
    • Therefore, the overall space complexity, dominated by the prefix count map, is O(n \times m^2) in the worst case, and typically better depending on the number of unique prefixes.

Method 2 - Using Trie

Here are the steps:

  1. Initialize Trie and Result Array:
    • Create the root node of the Trie.
    • Initialize the result array to store scores for each word.
  2. Build the Trie:
    • For each word in the input list:
      • Reset the pointer to the root node of the Trie.
      • For each character in the word:
        • Calculate its index (position) in the array.
        • If the corresponding child node does not exist, create it.
        • Increment the visited counter for the child node.
        • Move the pointer to the child node.
  3. Calculate Scores:
    • For each word in the input list:
      • Reset the pointer to the root node of the Trie.
      • Initialize a variable to accumulate the score for the current word.
      • For each character in the word:
        • Calculate its index (position) in the array.
        • Add the visited count of the corresponding child node to the score.
        • Move the pointer to the child node.
      • Store the accumulated score in the result array.
  4. Return the Result:
    • Return the result array containing the scores for each word.

Code

 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
35
36
37
38

class Trie {
    Trie[] ch = new Trie[26];
    int visited = 0;
}

class Solution {
    public int[] sumPrefixScores(String[] words) {
        Trie trie = new Trie();
        int[] ans = new int[words.length];

        // Build the Trie and count visits
        for (String word : words) {
            Trie t = trie;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (t.ch[idx] == null)
                    t.ch[idx] = new Trie();
                t.ch[idx].visited++;
                t = t.ch[idx];
            }
        }

        // Calculate the sum of prefix scores
        int k = 0;
        for (String word : words) {
            Trie t = trie;
            int curr = 0;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                curr += t.ch[idx].visited;
                t = t.ch[idx];
            }
            ans[k++] = curr;
        }

        return ans;
    }
}
 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
35
36
37
38
39
40

class Trie:
    def __init__(self):
        # Each node has a dictionary for children
        self.children = {}
        # Counter to keep track of how many times this node has been visited
        self.visited = 0


# Main Solution class
class Solution:
    # Method to calculate the sum of prefix scores
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        trie = Trie()  # Root of the Trie

        # Build the Trie and count visits
        for word in words:
            t = trie  # Start from the root for each word
            for char in word:  # Iterate over each character in the word
                # If the character is not already a child of the current node, add it
                if char not in t.children:
                    t.children[char] = Trie()
                t.children[char].visited += 1  # Increment the visited counter
                t = t.children[char]  # Move to the next node

        # Calculate the sum of prefix scores for each word
        result = []  # List to store the result
        for word in words:
            t = trie  # Start from the root for each word
            curr = 0  # Variable to accumulate the score for the current word
            for char in word:  # Iterate over each character in the word
                if char in t.children:
                    curr += t.children[
                        char
                    ].visited  # Add the visited counter to the score
                    t = t.children[char]  # Move to the next node
            result.append(
                curr
            )  # Append the accumulated score to the result list

        return result  # Return the final result list

Complexity

  • ⏰ Time complexity: O(n * m)
    • Building the Trie: For each word of average length m, inserting it into the Trie takes O(m) time. Doing this for n words results in O(n * m).
    • Calculating Scores: For each word, traversing the Trie to calculate the score also takes O(m) time. Thus, for n words, this also results in O(n * m).
    • Therefore, the overall time complexity is O(n * m).
  • 🧺 Space complexity: O(n*m)
    • In the worst case, the Trie could store every unique prefix of every word. This is generally more space-efficient than storing all prefixes in a map, but still can be bounded by O(n * m), where we store each prefix node along with its count.