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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Prefix Scores of Strings

Difficulty: Hard

Problem Description

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]. Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Key Insights

  • Each string can have multiple prefixes, and each prefix can contribute to the overall score based on how many strings have that prefix.
  • A Trie (prefix tree) is a suitable data structure for efficiently storing prefixes and counting their occurrences.
  • By inserting each word into the Trie, we can calculate the prefix scores for all prefixes of each word in linear time relative to the total length of the words.

Space and Time Complexity

Time Complexity: O(N * M), where N is the number of words and M is the maximum length of the words. Each word is processed character by character while building the Trie and calculating scores.

Space Complexity: O(N * M) for the Trie structure, where N is the number of words and M is the maximum length of the words.

Solution

To solve the problem, we will use a Trie data structure to store all the prefixes of the words. For each word, we will traverse through its prefixes and update the score based on the number of words that share the same prefix.

  1. Trie Structure: Create a TrieNode class to represent each node in the Trie. Each node will contain a dictionary of children and a count of how many words pass through that node.
  2. Insert Words: For each word, insert it into the Trie character by character, updating the count at each node.
  3. Calculate Scores: For each word, iterate through its prefixes and sum up the scores from the Trie to generate the final answer.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1

    def get_prefix_score(self, word):
        node = self.root
        score_sum = 0
        for char in word:
            if char in node.children:
                node = node.children[char]
                score_sum += node.count
        return score_sum

def sum_prefix_scores(words):
    trie = Trie()
    answer = []

    for word in words:
        trie.insert(word)

    for word in words:
        score = 0
        for i in range(len(word)):
            score += trie.get_prefix_score(word[:i + 1])
        answer.append(score)

    return answer
← Back to All Questions