All problems

Worn Label Matches

Medium · trie

A library prints shelf labels as short strings of lowercase letters. Over the years, some labels have rubbed away and one character of them can no longer be read; the reader writes such a spot as ?. A label has at most one ?.

A scanner reads a clean code from a book, a string of lowercase letters. The code fits a label when both have the same length and every position holds the same letter, except at the ?, where any letter is allowed. A label with no ? fits only a code equal to it.

You are given the list labels of shelf labels (the same label may appear several times, once per shelf) and the list queries of scanned codes. Return a list with one number per query, in the same order: how many entries of labels the code fits. Repeated labels are counted every time.

Examples

Example 1

Input: labels = ["a?c", "abc", "?bd", "abc"], queries = ["abc", "zbd", "ab"]

Output: [3, 1, 0]

"abc" fits "a?c" and both copies of "abc". "zbd" fits only "?bd". "ab" is shorter than every label, so it fits none.

Example 2

Input: labels = ["?"], queries = ["x", "xy"]

Output: [1, 0]

A single worn character fits any one letter, but not a longer code.

Constraints

• 1 <= len(labels) <= 2000
• 1 <= len(queries) <= 2000
• 1 <= len(labels[i]) <= 10
• 1 <= len(queries[i]) <= 10
• Labels contain lowercase letters and at most one ?.
• Queries contain only lowercase letters.