Expert · Data structures · 262 of 264
Autocomplete counts
Read a list of words, then answer queries: how many of the words start with the given prefix? Build a trie (a tree of letters) that stores a count at each node.
Input: n, then n words, then q, then q prefixes. Output: one count per prefix.
Examples
Input
5 apple app apply banana band 4 app ban c apple
Output
3 2 0 1
Input
1 x 2 x xy
Output
1 0
One more test checks other inputs when you press Check.
Stuck? The idea behind data structures
Choose the structure for what you do most: a heap (heapq) gives the smallest item fast, a deque adds and removes at both ends, a dictionary finds by key.
Two heaps, one for each half, keep the middle value of a stream of numbers.
import heapq
h = []
for x in [5, 1, 8, 3]:
heapq.heappush(h, x)
print(heapq.heappop(h), heapq.heappop(h)) # 1 3Watch for: heapq keeps the smallest first: for the largest, push -x and turn it back when you pop.