All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Tries
/

Tries

Problem
Editorial
Analytics

We're going to make our own Contacts application! The application must perform two types of operations:

  1. add name, where name is a string denoting a contact name. This must store name as a new contact in the application.
  2. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting with partial and print the count on a new line.

Given n sequential add and find operations, perform each operation in order.

Input Format:

The first line contains a single integer, n, denoting the number of operations to perform. 
Each line i of the n subsequent lines contains an operation in one of the two forms defined above.

Output Format

For each find partial operation, print the number of contact names starting with partial on a new line.

Constraints

  • 1 <= n <= 105
  • 1 <= |name| <=21
  • 1 <= |partial| <=21
  • It is guaranteed that name and partial contain lowercase English letters only.
  • The input doesn't have any duplicate name for the add operation.

 

SAMPLE INPUT
4
add hack
add hackerrank
find hac
find hak
SAMPLE OUTPUT
2
0
Explanation

Explanation

We perform the following sequence of operations:

  1. Add a contact named hack.
  2. Add a contact named hackerearth.
  3. Find and print the number of contact names beginning with hac. There are currently two contact names in the application and both of them start with hac, so we print 2 on a new line.
  4. Find and print the number of contact names beginning with hak. There are currently two contact names in the application but neither of them start with hak, so we print 0 on a new line.
Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?