⚡Flashcard Drill➔
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

  1. Build a trie where each node stores how many words pass through it.
  2. That count is exactly the number of words having the node's prefix.
  3. Then for each word, walk down the trie summing the node counts along its path.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Tries Problems