https://www.hackerrank.com/challenges/contacts

triecode.java

/**
 * Created by Abhiroj on 11/7/2016.
 */

import java.io.*;
import java.util.InputMismatchException;

public class triecode {


    static class Node{
        Node[] ref=new Node[26];
        boolean isWord=false;
        char c='\0';
    }

    static class Trie{
        Node  start;
        boolean visit[]=new boolean[26];
        public Trie(){
            start=new Node();
        }

        public int getIndex(char c)
        {

            return (int)(c-97);
        }

        public void markvisit(char c)
        {
            visit[getIndex(c)]=true;
        }

        public boolean usedInQuetion(char c)
        {
            return visit[getIndex(c)];
        }

        public void addWord(String word)
        {
            Node parentnode=start;
            char a=word.charAt(0);
            String b=word.substring(1,word.length());
            //collison, crawl until null pointer found
            while((parentnode.ref[getIndex(a)]!=null && b.length()>0)) {
                parentnode = parentnode.ref[getIndex(a)]; //crawled to next node
                a = b.charAt(0);
                b = b.substring(1, b.length());
            }
            //for null , insert remaining characters based on null move
            while((parentnode.ref[getIndex(a)]==null) && b.length()>=0)
            {
                Node newNode = new Node();
                newNode.c = a;
                if (b.length() == 0) newNode.isWord = true;
                parentnode.ref[getIndex(a)]=newNode;
                parentnode=newNode;
                markvisit(a);
                if(b.length()>0) {
                    a = b.charAt(0);
                    b = b.substring(1, b.length());
                }
                else break;
            }
        }

        public boolean findWord(String word,Node parentNode)
        {
            Node node=parentNode;
            char a=word.charAt(0);
            String b=word.substring(1, word.length());
            if(node.ref[getIndex(a)]!=null)
            {
                if(b.length()>0)
             return findWord(b, node.ref[getIndex(a)])||false;
                else
                {
                node=node.ref[getIndex(a)];
                    if(node.isWord) return true;
                    return false;
                }
            }
            else if(node.isWord) return true;
            return false;
        }

        public int countPartial(String partial,Node startNode)
        {
            Node node=startNode;
            char a=partial.charAt(0);
            String b=partial.substring(1, partial.length());
            while((node.ref[getIndex(a)]!=null && b.length()>0)) {
                node = node.ref[getIndex(a)]; //crawled to next node if not null
                a = b.charAt(0);
                b = b.substring(1, b.length());
                if(b.length()==0)
                {
                    if(node.ref[getIndex(a)]!=null)node = node.ref[getIndex(a)]; //crawled to next node in case it is the last character of the partial, then DFS
                else return 0; //because if it is null, then no further characters are present, that means string with this prefix does not exist
                }
            }
            return DFS(node);
        }

        public int DFS(Node node)
        {
            char forDebuggin=node.c;
            int count=0;
            if(node.isWord)
            count+=1;
            for (Node a:node.ref)
            {
                if((a!=null) && (usedInQuetion(a.c))) //visit only those chars which are used once or more in the problem
                {
                    char forDeb=a.c;
                    count=count+DFS(a);
                }
            }
            return count;
        }

    }


    public static void main(String args[]) {
        InputReader in = new InputReader(System.in);
        OutputWriter out = new OutputWriter(System.out);
        int n=in.nextInt();
        Trie trie=new Trie();
        while(n-->0)
        {
          String comm=in.next();
          String word=in.next();
            if(comm.equals("add"))
            {
                trie.addWord(word);
            }
            else
            {
                System.out.println(trie.countPartial(word, trie.start));
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c & 15;

                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextInt();

            return array;
        }

        public long nextLong() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sign = 1;

            if (c == '-') {
                sign = -1;

                c = read();
            }

            long result = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                result *= 10;
                result += c & 15;

                c = read();
            } while (!isSpaceChar(c));

            return result * sign;
        }

        public long[] nextLongArray(int arraySize) {
            long array[] = new long[arraySize];

            for (int i = 0; i < arraySize; i++)
                array[i] = nextLong();

            return array;
        }

        public float nextFloat() // problematic
        {
            float result, div;
            byte c;

            result = 0;
            div = 1;
            c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean isNegative = (c == '-');

            if (isNegative)
                c = (byte) read();

            do {
                result = result * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    result += (c - '0') / (div *= 10);

            if (isNegative)
                return -result;

            return result;
        }

        public double nextDouble() // not completely accurate
        {
            double ret = 0, div = 1;
            byte c = (byte) read();

            while (c <= ' ')
                c = (byte) read();

            boolean neg = (c == '-');

            if (neg)
                c = (byte) read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');

            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);

            if (neg)
                return -ret;

            return ret;
        }

        public String next() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            StringBuilder res = new StringBuilder();

            do {
                res.appendCodePoint(c);

                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String nextLine() {
            int c = read();

            StringBuilder result = new StringBuilder();

            do {
                result.appendCodePoint(c);

                c = read();
            } while (!isNewLine(c));

            return result.toString();
        }

        public boolean isNewLine(int c) {
            return c == '\n';
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    static class OutputWriter {
        private PrintWriter writer;

        public OutputWriter(OutputStream stream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                    stream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void println(int x) {
            writer.println(x);
        }

        public void print(int x) {
            writer.print(x);
        }

        public void println(int array[], int size) {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(int array[], int size) {
            for (int i = 0; i < size; i++)
                print(array[i] + " ");
        }

        public void println(long x) {
            writer.println(x);
        }

        public void print(long x) {
            writer.print(x);
        }

        public void println(long array[], int size) {
            for (int i = 0; i < size; i++)
                println(array[i]);
        }

        public void print(long array[], int size) {
            for (int i = 0; i < size; i++)
                print(array[i]);
        }

        public void println(float num) {
            writer.println(num);
        }

        public void print(float num) {
            writer.print(num);
        }

        public void println(double num) {
            writer.println(num);
        }

        public void print(double num) {
            writer.print(num);
        }

        public void println(String s) {
            writer.println(s);
        }

        public void print(String s) {
            writer.print(s);
        }

        public void println() {
            writer.println();
        }

        public void printSpace() {
            writer.print(" ");
        }

        public void flush() {
            writer.flush();
        }

        public void close() {
            writer.close();
        }

    }

    static class CMath {
        static long power(long number, long power) {
            if (number == 1 || number == 0 || power == 0)
                return 1;

            if (power == 1)
                return number;

            if (power % 2 == 0)
                return power(number * number, power / 2);
            else
                return power(number * number, power / 2) * number;
        }

        static long modPower(long number, long power, long mod) {
            if (number == 1 || number == 0 || power == 0)
                return 1;

            number = mod(number, mod);

            if (power == 1)
                return number;

            long square = mod(number * number, mod);

            if (power % 2 == 0)
                return modPower(square, power / 2, mod);
            else
                return mod(modPower(square, power / 2, mod) * number, mod);
        }

        static long moduloInverse(long number, long mod) {
            return modPower(number, mod - 2, mod);
        }

        static long mod(long number, long mod) {
            return number - (number / mod) * mod;
        }

    }
}