936. Prefix Score Totals
In a spelling contest every word earns a score. For each non-empty prefix of the word, count how many entries of the list words start with that prefix, then add those counts together. The word itself is one of the entries (so every prefix counts at least once), and every duplicate in the list counts separately.
Return an array whose i-th value is the score of words[i]. An empty word has no non-empty prefixes and scores 0. Scores are small enough to fit in a normal 32-bit integer. Counting each prefix by scanning the whole list is too slow; aim for time linear in the total number of characters.
Example 1
- Input:
- words = ["pip","pi","pit"]
- Output:
- [7,6,7]
- Explanation:
pip: p appears 3 times, pi 3, pip 1, total 7.pi: 3+3=6.pit: 3+3+1=7.
Example 2
- Input:
- words = ["ant","bat","ant"]
- Output:
- [6,3,6]
- Explanation:
antscores 2+2+2=6 (both copies count),batscores 1+1+1=3.
Example 3
- Input:
- words = ["wd","","wdwd"]
- Output:
- [4,0,6]
- Explanation:
The empty word has no prefixes and scores 0;
wdscores 2+2=4 andwdwdscores 2+2+1+1=6.
Constraints
1 ≤ words.length ≤ 8000
0 ≤ words[i].length ≤ 15 (total length at most 2 * 105 in general)
Words consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(total characters)
- Space
- O(total characters)