You are given a dictionary that initially contains no words. You need to process a series of queries, each falling into one of two types:
- Type 1 query: Add a word to the dictionary.
1 word(1 ≤ |word| ≤ 1000), where
wordis a non-empty string consisting of lowercase English letters.
- Action: Add the word to the dictionary.
- Type 2 query: Count the number of words starting with a given prefix.
2 prefix(1 ≤ |prefix| ≤ 1000), where
prefixis a non-empty string consisting of lowercase English letters.
- Output: Output the number of words in the dictionary that start with the given prefix.
You need to implement a program that processes these queries efficiently.
The first line of the input contains a single integer, n (), representing the number of queries.
The following n lines contain the queries. Each line is in one of the following formats:
1 wordfor a Type 1 query.
2 prefixfor a Type 2 query.
It is guaranteed that the total number of characters in the input does not exceed .
For each Type 2 query, output a single integer on a new line representing the number of words in the dictionary that start with the given prefix.
7 1 aba 1 abac 1 caba 2 ab 1 caba 1 cd 2 c
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB