LeetCode 2416 - Sum of Prefix Scores of Strings
The problem is asking us to compute a special score for each string in a list of strings. Specifically, for a string term, its score is defined as the number of strings in the array that have term as a prefix.
Difficulty: 🔴 Hard
Topics: Array, String, Trie, Counting
Solution
Problem Understanding
The problem is asking us to compute a special score for each string in a list of strings. Specifically, for a string term, its score is defined as the number of strings in the array that have term as a prefix. The main task is to compute, for each string in the list, the sum of the scores of all its non-empty prefixes.
For instance, if words = ["abc", "ab", "bc", "b"], we consider the prefixes "a", "ab", "abc" for "abc", and count how many words in the list start with each prefix. Summing these counts gives the final score for that string. The output should be an array of these sums, maintaining the order of the input.
The input consists of up to 1000 strings, each with a length up to 1000 characters. The constraints imply that a naive approach comparing each prefix of every string against all strings may be too slow, because it would result in roughly $O(n^2 \cdot L^2)$ operations in the worst case, where $L$ is the maximum string length. The problem guarantees non-empty strings and lowercase letters only, which simplifies prefix handling and allows trie-based optimizations.
Important edge cases include single-character strings, repeated strings, and strings that share common prefixes extensively, as these could produce high counts if not handled efficiently.
Approaches
The brute-force approach would iterate over each string, extract all non-empty prefixes, and then for each prefix, iterate over all strings in the array to count matches. This works correctly because it explicitly counts every prefix occurrence, but it is inefficient due to repeated scanning over all strings for every prefix.
The optimal approach uses a Trie (prefix tree) to aggregate prefix counts efficiently. Each node in the trie keeps track of how many words pass through it. By inserting all words into the trie and incrementing counts along the path, we can later compute the score of any prefix in constant time relative to its length. Summing the scores of all prefixes of a word becomes a simple traversal along its path in the trie.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2 * L) | O(1) | Compare each prefix against all words, too slow for n=L=1000 |
| Optimal | O(n * L) | O(n * L) | Trie-based solution, counts prefixes efficiently |
Algorithm Walkthrough
- Initialize a Trie: Create a root node with an empty dictionary for children and a counter initialized to zero. The counter will store the number of words passing through the node.
- Insert all words into the Trie: For each word, start from the root and iterate over its characters. For each character:
- If the character is not in the current node's children, create a new node.
- Move to the child node corresponding to the character.
- Increment the node's counter by 1. This counter now represents the number of words having this prefix.
- Calculate prefix sums for each word: For each word, traverse the trie following its characters. At each node, add its counter to a running sum. This sum represents the total score of all prefixes of that word.
- Return the results: Collect the computed sums in a list or slice and return it as the answer.
Why it works: The trie ensures that all prefixes are stored in a hierarchical structure. Each node’s counter accurately tracks how many words share that prefix. By traversing each word's path in the trie, we efficiently sum the counts of all its prefixes without redundant comparisons.
Python Solution
from typing import List
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
root = TrieNode()
# Build the Trie and count prefixes
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.count += 1
# Calculate sum of prefix scores
result = []
for word in words:
node = root
total = 0
for char in word:
node = node.children[char]
total += node.count
result.append(total)
return result
Implementation Walkthrough: We define a TrieNode class to hold children and a prefix count. First, we insert all words into the trie, incrementing counts along the path. Next, for each word, we traverse the trie and sum the counts of all nodes along its path, producing the desired sum of prefix scores.
Go Solution
type TrieNode struct {
children map[rune]*TrieNode
count int
}
func sumPrefixScores(words []string) []int {
root := &TrieNode{children: make(map[rune]*TrieNode)}
// Build Trie and count prefixes
for _, word := range words {
node := root
for _, ch := range word {
if node.children[ch] == nil {
node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[ch]
node.count++
}
}
// Calculate sum of prefix scores
result := make([]int, len(words))
for i, word := range words {
node := root
total := 0
for _, ch := range word {
node = node.children[ch]
total += node.count
}
result[i] = total
}
return result
}
Go-specific notes: Go requires explicit initialization of maps in TrieNode. We also handle runes explicitly when iterating over strings to support Unicode correctly, although lowercase English letters suffice for this problem. Slices are used for results.
Worked Examples
Example: words = ["abc","ab","bc","b"]
- Insert "abc" → counts updated: a:1, b:1, c:1
- Insert "ab" → counts updated: a:2, b:2
- Insert "bc" → counts updated: b:3, c:2
- Insert "b" → counts updated: b:4
Prefix sums:
| Word | Prefixes | Counts | Sum |
|---|---|---|---|
| "abc" | a, ab, abc | 2, 2, 1 | 5 |
| "ab" | a, ab | 2, 2 | 4 |
| "bc" | b, bc | 4, 1 | 5 (matches previous explanation should be 3, careful) |
Carefully, correct counts are:
- a: appears in "abc","ab" → 2
- ab: appears in "abc","ab" → 2
- abc: appears in "abc" → 1
- b: appears in "b","bc" → 2
- bc: appears in "bc" → 1
Thus sums match problem description: [5,4,3,2].
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n * L) | Inserting all words into the trie and computing prefix sums is linear in total characters |
| Space | O(n * L) | Trie stores all characters of all words |
The algorithm scales efficiently with both the number of words and their lengths.
Test Cases
# Provided examples
assert Solution().sumPrefixScores(["abc","ab","bc","b"]) == [5,4,3,2]
assert Solution().sumPrefixScores(["abcd"]) == [4]
# Single character strings
assert Solution().sumPrefixScores(["a","b","c"]) == [1,1,1]
# Repeated words
assert Solution().sumPrefixScores(["aa","aa","aa"]) == [6,6,6]
# Nested prefixes
assert Solution().sumPrefixScores(["a","aa","aaa"]) == [3,5,6]
# Max length word
long_word = ["a"*1000]
assert Solution().sumPrefixScores(long_word) == [1000]
| Test | Why |
|---|---|
| ["abc","ab","bc","b"] | Base case with shared prefixes |
| ["abcd"] | Single word, multiple prefixes |
| ["a","b","c"] | Single-character strings |
| ["aa","aa","aa"] | Repeated words to test counting |
| ["a","aa","aaa"] | Nested prefixes to test accumulation |
| ["a"*1000] | Max length word to test performance |
Edge Cases
Single-character words: They are valid prefixes themselves and may overlap with other words starting with the same character. The implementation correctly counts them by traversing the trie.
Repeated words: When words repeat, all prefixes' counts are incremented multiple times. The trie nodes correctly accumulate counts, ensuring sums are accurate for duplicates.
Very long words: Words of length 1000 stress both time and space. Using a trie avoids repeated comparisons, keeping the time complexity linear relative to total characters rather than quadratic.
This solution handles all these edge cases correctly while remaining efficient.