955. How Many Words a Pattern Matches

A fixed list of n words is given, then q patterns. A pattern is made of lowercase letters and dots, where a dot stands for exactly one letter of any kind. For each pattern print how many of the n words it matches. A word matches when it has the same length as the pattern and agrees with it at every position that is not a dot.

The list may contain the same word more than once, and each copy counts.

words bad dad mad bat bar, patterns .ad, ba., ... -> 3, 3, 5 words ab ab cd, patterns ab, .. -> 2, 3 words abc abd, patterns abx, ab., ab -> 0, 2, 0

The third line ends with a pattern SHORTER than every word, which matches nothing, because a dot cannot stand for the missing character and a pattern never matches a longer word.

## What the direct method costs

Test each word against each pattern. With n = 20000, q = 2000 and words of up to 12 letters that is 4 * 10^8 character comparisons, and it repeats the same work for every pattern that begins the same way.

## Counting instead of stopping

Problem 954 answers yes or no and stops at the first hit. A count cannot stop, so the recursion returns a number and adds up what the branches return.

Store at each node how many words END there, as a count rather than a flag, so that repeated words are handled with no extra machinery.

count(node, k): if k == length(p): return endCount[node] if p[k] is '.': total = 0 for c in a .. z: if child[node][c] exists: total += count(child[node][c], k+1) return total c = p[k] if child[node][c] is absent: return 0 return count(child[node][c], k+1)

## Why adding the branches counts each word exactly once

Every word corresponds to exactly one path from the root, so a word is reachable by exactly one sequence of choices through the recursion. Two different branches of a dot lead into disjoint subtrees, because they start with different letters, so no word is ever counted by two branches. Summing is therefore a sum over disjoint sets, and the total is the number of matching words.

The end COUNT rather than an end flag is what makes duplicated words come out right: ab ab cd answers 2 for the pattern ab.

## Where the length check lives

It lives in the base case and nowhere else. The recursion only looks at endCount once k has reached the end of the pattern, so a word longer than the pattern is never counted, and a word shorter than the pattern is never reached, because the recursion falls off the trie looking for a child that the shorter word never created.

## The cost, honestly

A pattern that starts with a dot fans out over every first letter present, and one that is all dots visits every node whose depth is at most the pattern length. That is bounded by the trie size, at most 1 + 20000 * 12 = 240001 nodes, so a single query is O(nodes) in the worst case and O(length of the pattern) when there are no dots. Leading dots are the expensive ones; a dot at the END costs one level of fan out and no more.

## Overflow

Nothing here overflows. A count is at most n, which is 20000, and the sum of the branch counts at any node is at most that too, since the branches are disjoint.

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ q ≤ 2000` - Every word is 1 to 12 lowercase English letters, and words may repeat. - Every pattern is 1 to 12 characters, each a lowercase English letter or a `.`.