All problems

Postcode District Counts

Medium · trie

A delivery depot keeps a list codes of postcodes, each one a string of lowercase letters. The same postcode may appear several times, once for every parcel addressed there.

Planners ask about districts. A district is named by a short string, and a postcode belongs to it when the postcode starts with that string. A postcode equal to the whole name belongs to the district too.

You are given the list prefixes of district names. Return a list with one number per name, in the same order: how many entries of codes belong to that district. Repeated postcodes are counted every time they appear.

Examples

Example 1

Input: codes = ["cat", "car", "cart", "dog", "cat"], prefixes = ["ca", "cat", "d", "x"]

Output: [4, 2, 1, 0]

Four entries start with "ca" (the two "cat", "car" and "cart"). Two are exactly "cat". One starts with "d". None starts with "x".

Example 2

Input: codes = ["abc"], prefixes = ["abcd", "abc", "a"]

Output: [0, 1, 1]

A name longer than the postcode can never be a start of it, so "abcd" counts nothing.

Constraints

• 1 <= len(codes) <= 2000
• 1 <= len(prefixes) <= 2000
• 1 <= len(codes[i]) <= 10
• 1 <= len(prefixes[i]) <= 10
• Every string contains only lowercase letters.
• Codes may repeat.