from collections import defaultdict

class Node:
    def __init__(self):
        self.char = defaultdict(Node)
        self.count = 0
        
class Trie:
    def __init__(self):
        self.root = Node()
    
    def add(self, name: str) -> None:
        curr_node = self.root
        for c in name:
            curr_node = curr_node.char[c]
            curr_node.count += 1
        
    def find(self, name: str) -> int:
        curr_node = self.root
        for c in name:
            if c not in curr_node.char:
                return 0
            curr_node = curr_node.char[c]
        return curr_node.count

def contacts(queries):
    trie = Trie()
    result = []
    for op, name in queries:
        if op == 'add':
            trie.add(name)
        elif op == 'find':
            result.append(trie.find(name))
    return result

 class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        int count = 0;
    }

     class Result {
        public static List<Integer> contacts(List<List<String>> queries) {
            TrieNode root = new TrieNode();
            List<Integer> results = new ArrayList<>();

            for (List<String> query : queries) {
                String operation = query.get(0);
                String value = query.get(1);

                if (operation.equals("add")) {
                    addContact(root, value);
                } else if (operation.equals("find")) {
                    results.add(findPartial(root, value));
                }
            }

            return results;
        }

        private static void addContact(TrieNode root, String contact) {
            TrieNode current = root;
            for (char c : contact.toCharArray()) {
                current.children.putIfAbsent(c, new TrieNode());
                current = current.children.get(c);
                current.count++;
            }
        }

        private static int findPartial(TrieNode root, String prefix) {
            TrieNode current = root;
            for (char c : prefix.toCharArray()) {
                current = current.children.get(c);
                if (current == null) {
                    return 0;
                }
            }
            return current.count;
        }
    }

from collections import defaultdict
def contacts(queries):
    # Write your code here
    record = defaultdict(int)
    ans = []
    for operation, name in queries:
        if operation == 'add':
            for i in range(len(name)):
                record[name[:i+1]] += 1
        else:
            ans.append(record[name])
    return ans

class TrieNode:
    __slots__ = 'children', 'numberofwordsafter'
    def __init__(self):
        self.children = {}
        self.numberofwordsafter=0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        currentNode = self.root
        currentNode.numberofwordsafter +=1
        for c in word:
            if c not in currentNode.children:
                currentNode.children[c]=TrieNode()
            currentNode = currentNode.children[c]
            currentNode.numberofwordsafter +=1

    def numwords(self, word):
        cur_node = self.root
        for c in word:
            if c not in cur_node.children:
                return 0
            else:
                cur_node=cur_node.children[c]
        return cur_node.numberofwordsafter

def contacts(queries):
    # Write your code here
    names=Trie()
    results=[]
    for q in queries:
        if q[0]=='add':
            names.insert(q[1])
        else:
            res = names.numwords(q[1])
            results.append(res)
    return results

class TrieNode:
    def __init__(self, data):
        self.data = data
        self.children = {}
        self.freq = 0

def add_word(root, word):
    if len(word) == 0:
        return
    new_root = root.children.get(word[0], TrieNode(word[0]))
    new_root.freq = new_root.freq + 1
    root.children[word[0]] = new_root
    add_word(new_root, word[1:])
    
def find_word(root, word):
    if len(word) == 0:
        return root.freq
    
    if word[0] not in root.children:
        return 0
        
    return find_word(root.children[word[0]], word[1:])

def contacts(queries):
    found = []
    root = TrieNode('*')
    for query in queries:
        qtype, word = query[0], query[1]
        if qtype == 'add':
            add_word(root, word)
        else:
            found.append(find_word(root, word))
    return found