Sum of Prefix Scores of Strings

For each string, compute the sum of how many words share each of its prefixes. Pattern focus: Trie Prefix Counting. Each trie node stores how many words pass through it, making prefix-score accumulation straightforward.

Input Format

words = array of lowercase words

Output Format

prefix score for each word in input order

Constraints

  • 1 <= words.length <= 10^5
  • 1 <= total characters across all words <= 1e6
  • Words contain only lowercase English letters.

Examples

Example 1:

Input:

words = ["abc","ab","bc","b"]

Output:

[5,4,3,2]

Explanation:

Each word receives the sum of the counts of its prefixes.

Example 2:

Input:

words = ["a"]

Output:

[1]

Explanation:

A single word contributes one to each of its prefixes.

Example 3:

Input:

words = ["aaa","a","aa"]

Output:

[6,3,5]

Explanation:

Repeated prefixes increase the score of longer words.

Loading...
Sum of Prefix Scores of Strings - Trie