2416. Sum of Prefix Scores of Strings Hard

1/**
2 * [2416] Sum of Prefix Scores of Strings
3 *
4 * You are given an array words of size n consisting of non-empty strings.
5 * We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].
6 * 
7 * 	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".
8 * 
9 * Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].
10 * Note that a string is considered as a prefix of itself.
11 *  
12 * Example 1:
13 * 
14 * Input: words = ["abc","ab","bc","b"]
15 * Output: [5,4,3,2]
16 * Explanation: The answer for each string is the following:
17 * - "abc" has 3 prefixes: "a", "ab", and "abc".
18 * - There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
19 * The total is answer[0] = 2 + 2 + 1 = 5.
20 * - "ab" has 2 prefixes: "a" and "ab".
21 * - There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
22 * The total is answer[1] = 2 + 2 = 4.
23 * - "bc" has 2 prefixes: "b" and "bc".
24 * - There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
25 * The total is answer[2] = 2 + 1 = 3.
26 * - "b" has 1 prefix: "b".
27 * - There are 2 strings with the prefix "b".
28 * The total is answer[3] = 2.
29 * 
30 * Example 2:
31 * 
32 * Input: words = ["abcd"]
33 * Output: [4]
34 * Explanation:
35 * "abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
36 * Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= words.length <= 1000
42 * 	1 <= words[i].length <= 1000
43 * 	words[i] consists of lowercase English letters.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/sum-of-prefix-scores-of-strings/
49// discuss: https://leetcode.com/problems/sum-of-prefix-scores-of-strings/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn sum_prefix_scores(words: Vec<String>) -> Vec<i32> {
55        vec![]
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2416() {
67    }
68}
69