Match the Abbreviations

Programmers shorten long words by replacing runs of letters with how many letters were left out: "internationalization" becomes "i18n", and "localization" can be written "l10n" or "lo3iz4n". An abbreviation is read from left to right: a letter must match the next letter of the word, and a number skips exactly that many letters. It matches a word when it uses up the whole word exactly.

Write count_matches(words, abbrs) that returns a list with one number for each abbreviation in abbrs: how many entries of words it matches.

A number in an abbreviation never starts with 0, so an abbreviation containing "0", "05" or "a01b" matches nothing.

Examples

count_matches(['internationalization', 'localization', 'location'], ['i18n', 'l10n', 'l6n', 'lo3iz4n'])
# returns [1, 1, 1, 1]
count_matches(['cat', 'cot', 'cut', 'dog'], ['c1t', '3', 'c2', 'd0g'])
# returns [3, 4, 3, 0]

In the second example "3" matches every three-letter word, and "d0g" matches nothing because its number starts with 0.

Constraints

• 0 <= len(words) <= 10,000. Each word has 1 to 20 lowercase English letters, and words may repeat: each copy counts.
• 0 <= len(abbrs) <= 2,000. Each abbreviation has 1 to 20 characters, all lowercase English letters and digits.
• Checking every abbreviation against every word is far too slow for the largest inputs.