928. Count Words with Given Prefix in Trie

Given a list of words and a list of query prefixes, return for each prefix the number of words that start with it. The input is JSON {words, prefixes}, and the output is an array of counts (one per prefix, in order).

Input: JSON {words, prefixes}.

Output: Array — the count of matching words per prefix.

Examples

Input: {"words":["apple","app","apply","banana"],"prefixes":["app","ban","z"]}
Output: [3,1,0]
Explanation: Counts for each prefix.

Input: {"words":["a","ab","abc"],"prefixes":["a","ab","abc","abcd"]}
Output: [3,2,1,0]
Explanation: Nested prefixes.

Input: {"words":["x"],"prefixes":["x","y"]}
Output: [1,0]
Explanation: Single word.

Constraints

• 1<=words<=10^4
• 1<=prefixes<=10^4

Asked by