Sum of Prefix Scores of Strings - Solution & Explanation
Problem Statement
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"is2, 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.
Example 1:
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:
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.
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 1000words[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You are given an array of strings. For each word, compute the sum of scores of all its prefixes. The score of a prefix is the number of words in the array that start with that prefix. The result for each word is the total score of every prefix it contains.
Approach 1: Hashtable for Counting Prefix Frequency (Time: O(n * L^2), Space: O(n * L^2))
This approach explicitly counts how many times every prefix appears using a hash map. Iterate through each word and generate all prefixes (word[:1], word[:2], ...). Store them in a hash table with their frequency. In a second pass, recompute each word's score by summing the counts of its prefixes from the map. The idea is straightforward and easy to implement using string operations and counting, but prefix generation repeatedly creates substrings, which increases both runtime and memory usage for long words.
Approach 2: Prefix Trie Construction (Time: O(N), Space: O(N))
A Trie stores prefixes efficiently while sharing common paths between words. Insert every word into the Trie character by character and maintain a counter at each node representing how many words pass through that prefix. After building the Trie, compute the score of a word by traversing its characters again and summing the stored counters at each node. Because each character is processed a constant number of times, the total work is proportional to the total number of characters N. This avoids repeated substring creation and naturally aggregates prefix counts.
Recommended for interviews: The Trie approach is the expected solution. It demonstrates understanding of prefix-based data structures and reduces the complexity to O(N). Starting with the hash map prefix counting approach shows that you understand the scoring rule, but the Trie solution proves you can optimize prefix aggregation efficiently.
Approach 1: Prefix Trie Construction
A Trie is an efficient tree-like data structure that allows efficient retrieval of a string's prefix scores. We start by inserting each word into the Trie, along with maintaining a count at each node to track how many words share that prefix. Then, for each word, we traverse its prefixes in the Trie to compute the prefix score by collecting the counts stored at each relevant node.
The solution builds a Trie from the list of given words. For each word, it inserts it into the Trie, incrementing the count of words at each node traversed. This helps track how many words share the same prefix. After building the Trie, it calculates the prefix score for each word by traversing its prefixes in the Trie and summing up the counts.
Complexity
The time complexity is O(n * m) where n is the number of words and m is the maximum length of the words, due to Trie insertions and lookups. The space complexity is O(N * m), N being the total length of all words combined, as each character might lead to a node in the Trie.
Approach 2: Hashtable for Counting Prefix Frequency
We can also use a hashtable (or dictionary) to count how often each prefix appears in the list of words. Iterate through each word and generate all its prefixes, updating their counts in the hashtable. Afterwards, compute the sum of counts for each full word by referencing its prefixes in the hashtable.
The C solution uses a hash table to keep track of prefix counts. For every word, we insert each of its prefixes into the hash table, updating their counts. Then, by iterating over prefixes of each word and retrieving their counts from the hash table, it calculates the prefix scores.
Complexity
Time complexity is O(n * m) as we process each prefix per word insertion and retrieval. Space complexity is potentially O(N * m), accounting for hash table storage of prefixes.
Approach 3: Prefix Tree
We can use a prefix tree to maintain all prefixes of the strings and count the occurrences of each prefix.
Define the prefix tree node structure Trie, which includes two properties:
children: An array of length 26 used to store the current node's children.cnt: The occurrence count of the current node.
Define two methods for the prefix tree:
insert: Inserts a string, adding its prefixes into the prefix tree.search: Searches for a string and returns the occurrence count of its prefixes.
We traverse all strings, inserting each string into the prefix tree. Then we traverse all strings again, calling the search method for each string and summing up the occurrence counts of each prefix.
Time complexity is O(L), and space complexity is O(L), where L is the total length of all strings.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Trie Construction | The time complexity is O(n * m) where n is the number of words and m is the maximum length of the words, due to Trie insertions and lookups. The space complexity is O(N * m), N being the total length of all words combined, as each character might lead to a node in the Trie. |
| Hashtable for Counting Prefix Frequency | Time complexity is O(n * m) as we process each prefix per word insertion and retrieval. Space complexity is potentially O(N * m), accounting for hash table storage of prefixes. |
| Prefix Tree | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashtable for Counting Prefix Frequency | O(n * L^2) | O(n * L^2) | Simple implementation when constraints are small or when avoiding custom data structures |
| Prefix Trie Construction | O(N) | O(N) | Best for large datasets with many shared prefixes; optimal interview solution |
Video Solution
Sum of Prefix Scores of Strings - Leetcode 2416 - Python • NeetCodeIO • 9,571 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sum of Prefix Scores of Strings easy or hard?
Sum of Prefix Scores of Strings Python/Java solution
How to solve Sum of Prefix Scores of Strings in O(n)?
What is the best approach for Sum of Prefix Scores of Strings?
Is Sum of Prefix Scores of Strings asked at Google/Amazon/Meta?
What data structure is used in Sum of Prefix Scores of Strings?
What is the time complexity of Sum of Prefix Scores of Strings?
Ready to solve this problem?
Practice Sum of Prefix Scores of Strings with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor