Implement Trie II — Count Words With a Prefix

Given a list of words, count how many of them start with a given prefix.

Example

Input: words apple app application apply banana, prefix app Output: 4 (apple, app, application, apply all start with "app"; banana doesn't)

Approach

A plain trie only tells you whether a prefix exists, not how many words pass through it. Add a counter to every node, incremented every time a word's insertion walks through it. Answering a query is then just: walk to the prefix's node (if it exists at all) and read its counter — O(prefix length) per query, no matter how many words were inserted.

Input format

Line 1: the words, space-separated Line 2: the prefix to query

Print the count.