NeetCode #483LC-2416HardTries
← Back to All Problems#483 · #2416 · Sum of Prefix Scores of Strings(字符串的前缀分数和)
📌 Problem Statement & Constraints
You are given an array of strings
words. For each word, the score is the sum over all its prefixes p of the number of words in the array that have p as a prefix. Return the scores. Constraints: 1 <= words.length <= 1000, 1 <= words[i].length <= 1000, total length at most 10^6.💡 Core Algorithmic Approaches
- Build a trie where each node stores how many words pass through it.
- That count is exactly the number of words having the node's prefix.
- Then for each word, walk down the trie summing the node counts along its path.
- This is O(total characters) for the build plus O(total characters) for the queries.
💻 Benchmark Python3 Implementation
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
root = {}
for w in words:
node = root
for ch in w:
# each node holds [pass-through count, children]
if ch not in node:
node[ch] = [0, {}]
node[ch][0] += 1 # one more word shares this prefix
node = node[ch][1]
res = []
for w in words:
node = root
total = 0
for ch in w:
child = node[ch] # child = [count, children]
total += child[0] # words sharing this prefix
node = child[1]
res.append(total)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total characters): one pass to build, one per word to query.
💾 Space Complexity
O(total characters) for the trie.
⚠️ Interview Pitfalls & Follow-ups
- Counting only complete words at each node: the score counts words having the prefix, not words equal to the prefix.
- Recomputing the count per prefix with a scan over all words: O(n^2 * L).
- Storing the count separately from the children: keeping them in one node structure avoids a second dictionary lookup per character.
- Forgetting to increment the count for the final character of each word: every character on the path, including the last, contributes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.