We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
importjava.util.Scanner;importjava.util.HashMap;publicclassSolution{publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intn=scan.nextInt();Trietrie=newTrie();for(inti=0;i<n;i++){Stringoperation=scan.next();Stringcontact=scan.next();if(operation.equals("add")){trie.add(contact);}elseif(operation.equals("find")){System.out.println(trie.find(contact));}}scan.close();}}classTrieNode{privateHashMap<Character,TrieNode>children=newHashMap<>();publicintsize=0;// this was the main trick to decrease runtime to pass tests.publicvoidputChildIfAbsent(charch){children.putIfAbsent(ch,newTrieNode());}publicTrieNodegetChild(charch){returnchildren.get(ch);}}classTrie{TrieNoderoot=newTrieNode();publicvoidadd(Stringstr){TrieNodecurr=root;for(charch:str.toCharArray()){curr.putChildIfAbsent(ch);curr=curr.getChild(ch);curr.size++;}}publicintfind(Stringprefix){TrieNodecurr=root;for(charch:prefix.toCharArray()){curr=curr.getChild(ch);if(curr==null){return0;}}returncurr.size;}}
Contacts
You are viewing a single comment's thread. Return to all comments →
Java solution - passes 100% of test cases
From my HackerRank solutions.
Let me know if you have any questions.