All problems

Prefix Popularity Score

Medium · trie

A search site keeps a list of words. weights[i] is how popular words[i] is. The same word may appear more than once in the list, each time with its own weight.

A typed query earns points from every word in the list. The points a word gives to a query are weights[i] multiplied by the number of leading letters the word and the query have in common (the length of their longest shared start). A word that shares nothing with the query gives 0.

The score of a query is the total of the points it earns from all the words. Return a list with the score of every query, in the order of queries.

Examples

Example 1

Input: words = ["car", "cat", "dog"], weights = [3, 2, 5], queries = ["car", "ca", "d", "x"]

Output: [13, 10, 5, 0]

The query "car" earns 3 * 3 = 9 from "car", 2 * 2 = 4 from "cat" and 0 from "dog". The query "ca" earns 3 * 2 + 2 * 2 = 10.

Example 2

Input: words = ["ab", "ab", "abc"], weights = [1, 2, 4], queries = ["abd"]

Output: [14]

The two copies of "ab" each share 2 letters with "abd": 1 * 2 + 2 * 2 = 6. The word "abc" also shares 2 letters: 4 * 2 = 8.

Example 3

Input: words = ["a"], weights = [5], queries = ["aaa"]

Output: [5]

The word and the query share only one leading letter, since the word has just one.

Constraints