SolutionTrie.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class SolutionTrie {

    private static Node word2Node(String word) {
        Node n = new Node();
        n.letter = word.charAt(0);
        if (word.length() != 1)
            n.children[word.charAt(1)-'a'] = word2Node(word.substring(1));
        //else
        n.count = 1;
        return n;
    }

    private static final class Node {
        public char letter;
        public Node[] children = new Node[26];
        public int count = 0;
    }
    
    private static final class Trie {
        public Node root = new Node();
        
        public void addWord(String word, Node node, int l) {
            node.count = node.count + 1;
            char c = word.charAt(0);
            Node n = node.children[c - 'a'];
            if (n != null) {
                //if (l == 1)
                //node.count = node.count + 1;
                //else
                if (l != 1)
                    addWord(word.substring(1), n, l-1);
            } else
                node.children[word.charAt(0) - 'a'] = word2Node(word);
        }
        
        public void addWord(String word) {
            addWord(word, root, word.length());
        }
        
        public int countChildren(Node node) {
            int sum = 0;
            Node n;
            for(int i=0; i<26; i++) {
                n = node.children[i];
                if (n != null)
                    sum += n.count + countChildren(n);
            }
            return sum;
        }
        
        public void find(String word, Node node, int l) {
            char c = word.charAt(0);
            Node n = node.children[c-'a'];
            if (n != null) {
                if (l == 1){
                    System.out.println(n.count);// + countChildren(n));
                } else {
                    find(word.substring(1), n, l-1);
                }
            } else {
                System.out.println(0);
            }
        }

        public void find(String word) {
            find(word, root, word.length());
        }
        
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int a0 = 0; a0 < n; a0++){
            String op = in.next();
            String contact = in.next();
            if ("add".equals(op)) {
                trie.addWord(contact);
            } else if ("find".equals(op)) {
                trie.find(contact);
            }
        }
    }
}