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.
If your tests are hanging/timing out/not finishing, you likely need a faster algorithm.
I keep a "size" at each node that keeps track of how many complete words can be made from that node. This makes my runtime faster since I don't have to recalculate the number of valid words from a node.
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();}}/* Based loosely on tutorial video in this problem */classTrieNode{privateHashMap<Character,TrieNode>children=newHashMap<>();publicintsize;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;}}
Tries: Contacts
You are viewing a single comment's thread. Return to all comments →
Java solution - passes 100% of test cases
I use a Trie.
If your tests are hanging/timing out/not finishing, you likely need a faster algorithm.
I keep a "size" at each node that keeps track of how many complete words can be made from that node. This makes my runtime faster since I don't have to recalculate the number of valid words from a node.
From my HackerRank Java solutions.