Interview Questions/Coding/Prefix Influence Scoreboard

Prefix Influence Scoreboard

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Prefix Influence Scoreboard

A search service scores each keyword using shared prefixes. For a word, consider every non-empty prefix of that word. The contribution of a prefix is the number of words in the full bank that start with that prefix. The score of a word is the sum of those prefix contributions. Scores must be returned in the same order as the input words. Input Format: You are given an array words. Output Format: Return an integer array containing the prefix influence score of each word.

Examples

Example 1

Input:

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

Output:

5 4 3 2

Explanation: abc -> a:2+ab:2+abc:1 = 5; ab -> a:2+ab:2 = 4; bc -> b:2+bc:1 = 3; b -> b:2 = 2. Thus the scores are 5 4 3 2.

Approach hint

Look for the state that actually matters after each operation.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp