Simple java code using Trie -

class TrieNode{ TrieNode[] children = new TrieNode[26]; int we,prefix; public TrieNode(){ we=0; prefix=0; for(int i=0;i<26;i++) children[i]=null; } }

class Result {

    public static TrieNode root = new TrieNode();
    static int c=0;

    public static void Insert(String s){
       TrieNode copy=root;
       for(int i=0;i<s.length();i++){
               int ch=s.charAt(i)-'a';
               if(copy.children[ch]==null)
               copy.children[ch]=new TrieNode();
               copy=copy.children[ch];
               copy.prefix++;
       }
       copy.we++;
       return;
    }

    public static int Search(String s){
            TrieNode copy=root;
            for(int i=0;i<s.length();i++){
                    int ch=s.charAt(i)-'a';
                    if(copy.children[ch]==null)
                    return 0;
                     copy=copy.children[ch];
            }
            c=copy.prefix;
            return c;
    }

public static List<Integer> contacts(List<List<String>> queries) {
// Write your code here
List<Integer> l=new ArrayList<Integer>();
for(List<String> i: queries){
if(i.get(0).equals("add"))
Insert(i.get(1));
else{
        c=0;
int count = Search(i.get(1));
l.add(count);
}
}
return l;

} }