2416. Sum of Prefix Scores of Strings LeetCode Solution

Last updated: February 27, 2025

In this guide, you will get 2416. Sum of Prefix Scores of Strings LeetCode Solution with the best time and space complexity. The solution to Sum of Prefix Scores of Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sum of Prefix Scores of Strings solution in C++
Sum of Prefix Scores of Strings solution in Java
Sum of Prefix Scores of Strings solution in Python
Additional Resources

2416. Sum of Prefix Scores of Strings LeetCode Solution image

Problem Statement of Sum of Prefix Scores of Strings

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].

For example, if words = [“a”, “ab”, “abc”, “cab”], then the score of “ab” is 2, since “ab” is a prefix of both “ab” and “abc”.

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].
Note that a string is considered as a prefix of itself.

Example 1:

Input: words = [“abc”,”ab”,”bc”,”b”]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
– “abc” has 3 prefixes: “a”, “ab”, and “abc”.
– There are 2 strings with the prefix “a”, 2 strings with the prefix “ab”, and 1 string with the prefix “abc”.
The total is answer[0] = 2 + 2 + 1 = 5.
– “ab” has 2 prefixes: “a” and “ab”.
– There are 2 strings with the prefix “a”, and 2 strings with the prefix “ab”.
The total is answer[1] = 2 + 2 = 4.
– “bc” has 2 prefixes: “b” and “bc”.
– There are 2 strings with the prefix “b”, and 1 string with the prefix “bc”.
The total is answer[2] = 2 + 1 = 3.
– “b” has 1 prefix: “b”.
– There are 2 strings with the prefix “b”.
The total is answer[3] = 2.

Example 2:

Input: words = [“abcd”]
Output: [4]
Explanation:
“abcd” has 4 prefixes: “a”, “ab”, “abc”, and “abcd”.
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists of lowercase English letters.

Complexity Analysis

Time Complexity: O(\Sigma |\texttt{words[i]}|)
Space Complexity: O(\Sigma |\texttt{words[i]}|)

2416. Sum of Prefix Scores of Strings LeetCode Solution in C++

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  int count = 0;
  TrieNode() : children(26) {}
};

class Solution {
 public:
  vector<int> sumPrefixScores(vector<string>& words) {
    vector<int> ans;

    for (const string& word : words)
      insert(word);

    for (const string& word : words)
      ans.push_back(getScore(word));

    return ans;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();

  void insert(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
      ++node->count;
    }
  }

  int getScore(const string& word) {
    shared_ptr<TrieNode> node = root;
    int score = 0;
    for (const char c : word) {
      node = node->children[c - 'a'];
      score += node->count;
    }
    return score;
  }
};
/* code provided by PROGIEZ */

2416. Sum of Prefix Scores of Strings LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public int count = 0;
}

class Solution {
  public int[] sumPrefixScores(String[] words) {
    int[] ans = new int[words.length];

    for (final String word : words)
      insert(word);

    for (int i = 0; i < words.length; ++i)
      ans[i] = getScore(words[i]);

    return ans;
  }

  private TrieNode root = new TrieNode();

  private void insert(String word) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - 'a';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
      ++node.count;
    }
  }

  private int getScore(String word) {
    TrieNode node = root;
    int score = 0;
    for (final char c : word.toCharArray()) {
      node = node.children[c - 'a'];
      score += node.count;
    }
    return score;
  }
}
// code provided by PROGIEZ

2416. Sum of Prefix Scores of Strings LeetCode Solution in Python

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}
    self.count = 0


class Solution:
  def sumPrefixScores(self, words: list[str]) -> list[int]:
    root = TrieNode()

    def insert(word: str) -> None:
      node: TrieNode = root
      for c in word:
        node = node.children.setdefault(c, TrieNode())
        node.count += 1

    for word in words:
      insert(word)

    def getScore(word: str) -> int:
      node: TrieNode = root
      score = 0
      for c in word:
        node = node.children[c]
        score += node.count
      return score

    return [getScore(word) for word in words]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents