Tries:Contacts.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class TriesContacts {

	static class Node {
		HashMap<Character, Node> links = null;
		boolean isFinish;
		int count;

		public Node() {
			links = new HashMap<>();
			isFinish = false;
		}
	}

	static class Trie {
		Node root;

		Trie() {
			root = new Node();
		}

		public void addData(String data) {
			Node current = root;
			Character currentChar = ' ';
			current.count++;
			for (int i = 0; i <= data.length(); i++) {
				if (i == data.length()) {
					current.isFinish = true;
					break;
				}
				currentChar = data.charAt(i);
				if (current.links.containsKey(currentChar)) {
					current = current.links.get(currentChar);
				} else {
					current.links.put(currentChar, new Node());
					current = current.links.get(currentChar);
				}
			}
		}

		public int findPartial(String data, Node current) {

			if (data.isEmpty()) {
				return current.count;
			}
			char first = data.charAt(0);
			return current.links.containsKey(first) ? findPartial(data.substring(1), current.links.get(first)) : 0;
		}
	}

	public static int findCount(Node root) {
		int count = 0;
		if (root.isFinish) {
			count++;
		}
		if (root.links != null) {
			for (Map.Entry<Character, Node> entry : root.links.entrySet()) {
				count += findCount(entry.getValue());
			}
		}
		return count;
	}

	public TriesContacts() {

	}

	static class Command {
		public String op;
		public String data;

		public Command(String op, String data) {
			this.op = op;
			this.data = data;
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		Trie trie = new Trie();
		ArrayList<Command> commands = new ArrayList<>();

		for (int a0 = 0; a0 < n; a0++) {
			String op = in.next();
			String contact = in.next();
			commands.add(new Command(op, contact));

		}
		for (int index = 0; index < commands.size(); index++) {
			if (commands.get(index).op.equals("add")) {
				trie.addData(commands.get(index).data);

			} else if (commands.get(index).op.equals("find")) {
				int count = trie.findPartial(commands.get(index).data, trie.root);
				System.out.println(count);

			} else {
				System.out.println("invalid input");
			}
		}

		in.close();
	}
}