Problem

You are given a list of n words and a list of q query strings. For each query p, return the number of words in the list that have p as a prefix (a word is a prefix of itself).

Input / Output

• Input: words[] (lowercase strings), queries[] (lowercase strings).
• Output: an integer array of length q, where the i-th value is the count for queries[i].

Examples

Example 1 Input: words = ["apple", "app", "apricot", "banana"], queries = ["ap", "app", "b", "c"] Output: [3, 2, 1, 0] Explanation: "ap" prefixes apple, app, apricot; "app" prefixes apple and app; "b" prefixes banana; nothing starts with "c".

Example 2 Input: words = ["a", "a", "ab"], queries = ["a"] Output: [3]

Constraints

• 1 <= n, q <= 10^5
• Total length of all words and queries <= 10^6.

Approach

Brute force compares every query against every word: O(n · q · L), far too slow.

Trie with subtree counts (recommended).

1. Insert every word into a trie. At each node passed during insertion, increment a count field — the number of words that pass through this node, i.e. the number of words having the node's path as a prefix.
2. For each query, walk down the trie character by character. If a character is missing, the answer is 0. Otherwise the answer is the count at the final node.

Every insertion and every query costs O(length of the string), independent of n.

Alternative — sorting + binary search. Sort the words. For a query p, all words with prefix p form a contiguous block: the first index is lowerBound(p) and the end is lowerBound(p + '{') ('{' is the character after 'z'). The count is the difference. Cost O((n + q) · L · log n).

Complexity (trie)

• Build: O(total characters in words)