We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Prefix Scores of Strings

Number: 2494

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg, Google

Problem Description

Given an array of non-empty strings, for each string compute the sum of scores of every non-empty prefix. The score of a prefix is defined as the number of words in the array for which that prefix is a prefix (including the word itself). For example, if words = ["abc","ab","bc","b"], then the score for "abc" is computed by considering its prefixes "a", "ab", and "abc" and summing the count of words starting with each of these prefixes.

Key Insights

  • Use a Trie (prefix tree) to efficiently store and count the occurrences of every prefix across all words.
  • Each node in the Trie will store a frequency count of how many words pass through that node.
  • First, build the Trie by inserting every word from the array.
  • Then, for each word, traverse the Trie along its characters to retrieve the prefix counts and sum them.
  • This approach avoids recomputation by leveraging the shared structure of prefixes.

Space and Time Complexity

Time Complexity: O(T) where T is the total number of characters across all words (in worst-case O(n*m), with n as number of words and m as average word length). Space Complexity: O(T) for the Trie that stores all characters and counts.

Solution

The solution uses a Trie data structure. We first build the Trie by inserting each word. When inserting a word, update the count at each node along the path, meaning that each node’s count represents the number of words that share that prefix. Then, for each word, traverse the Trie from the root following its characters, and sum up the counts for each prefix. The result is an array where each element corresponds to the total prefix score for that word.

Code Solutions

# Define a TrieNode class
class TrieNode:
    def __init__(self):
        self.children = {}  # Dictionary mapping char -> TrieNode
        self.count = 0      # Count of words that go through this node

# Insert word into the Trie, updating prefix counts
def insert(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
        node.count += 1

# Query the Trie to get the sum of prefix scores for the word
def query(root, word):
    node = root
    total = 0
    for char in word:
        node = node.children[char]
        total += node.count
    return total

def sumPrefixScores(words):
    # Initialize the Trie root
    root = TrieNode()
    # Build the Trie with all words
    for word in words:
        insert(root, word)
    
    result = []
    # For each word, compute the sum of prefix scores
    for word in words:
        result.append(query(root, word))
    return result

# Example usage:
words = ["abc", "ab", "bc", "b"]
print(sumPrefixScores(words))  # Output: [5, 4, 3, 2]
← Back to All Questions