Watch 10 video solutions for Sum of Prefix Scores of Strings, a hard level problem involving Array, String, Trie. This walkthrough by NeetCodeIO has 9,365 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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].
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.
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.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 | 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 |