トライ - コンタクト - Hackerrank

Question

私は現在hackerrank Tries - Contacts

にこの課題を解決しようとしていますそして、私のアルゴリズムは一つだけのテストケースのために失敗しました。テストケース＃1。このテストケースに合格するためには、変更する必要のあることについて、誰にでも洞察を伝えることができます。私は子ノードのハッシュマップを含むTrieNodeクラスを使用しています。また、各ノードのサイズを格納して、そこに含まれる単語の数を制限します。次のように

テストケース＃1は、次のとおりです。

add s 
add ss 
add sss 
add ssss 
add sssss 
find s 
find ss 
find sss 
find ssss 
find sssss 
find ssssss 

次のようにコードは次のとおりです。

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

public class Solution { 

    TrieNode root; 

    class TrieNode{ 
     Map<Character, TrieNode> children = new HashMap<Character, TrieNode>(); 
     int size=0; 
    } 

    public Solution(){ 
     root = new TrieNode(); 
    } 

    public void addWord(String word){ 
     TrieNode current = root; 
     for(int i=0;i<word.length();i++){ 
      char c = word.charAt(i); 
      if(!current.children.containsKey(c)){ 
       //create a new node 
       TrieNode temp = new TrieNode(); 
       //add the word to the current node's children 
       current.children.put(c, temp); 
       current.size++; 
       current = temp; 
      } 
      else{ 
       current.size++; 
       current = current.children.get(c); 
      } 
     } 
    } 

    public void prefixSearch(String letters){ 

     TrieNode current = root; 
     boolean sequenceExists = true; 

     for(int i=0; i<letters.length();i++){ 
      char c = letters.charAt(i); 
      if(current.children.containsKey(c)){ 
       if(i == letters.length()-1){ 
        System.out.println(current.size); 
        break; 
       } 
       else{ 
        current = current.children.get(c); 
       } 
      } 
      else{ 
       System.out.println(0); 
       break; 
      } 
     } 

    } 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int n = in.nextInt(); 
     Solution sol = new Solution(); 
     for(int a0 = 0; a0 < n; a0++){ 
      String op = in.next(); 
      String contact = in.next(); 

      if(op.equals("add")){ 
       if(contact.length() >=1 && contact.length() <=21) 
       sol.addWord(contact); 
      } 
      else if(op.equals("find")){ 
       if(contact.length() >=1 && contact.length() <=21) 
       sol.prefixSearch(contact); 
      } 
      else{ 
       //do nothing 
      } 
     } 
    } 
} 

Answer 1

あなたがトライに単語を追加するときは、最後の1を除いて、すべてのノードカウントインクリメント。

current.size++; 

をあなたのコードは、テストに合格した：これはオフずつhttps://en.wikipedia.org/wiki/Off-by-one_error

と呼ばれるエラーの種類は、（ループの後）addWordメソッドの最後にもう一度、この行を追加気づくするのは非常に一般的と難しいですケース0あなたのコードでは、この特定のバグはあなたがHAC-kerrankのような接頭辞を検索したときに表示されませんが、あなたはhackerran Kよう最後の文字を含む完全な単語を検索したときに表示さないためにまたはSSSS S

Answer 2

Iは、他のすべてがタイムアウトしている1 & 5、テストケース0を除いて、この溶液を有します。ここに私のJava 8での実装があります。すべてのテストケースに合格するためにコードを改善する必要があります

public class Contacts { 
    static Map<String, String> contactMap = new HashMap<>(); 
    public static void main(String[] args) { 
     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(op.equalsIgnoreCase("add")) { 
       addOrFind(contact, op); 
      } else { 
       addOrFind(contact, op); 
      } 
     } 
    } 

    public static void addOrFind(String name, String type) { 
     if(type.equalsIgnoreCase("add")) { 
      contactMap.put(name, name); 
     } else { 
      long count = contactMap.entrySet().stream() 
        .filter(p->p.getKey().contains(name)).count(); 
      System.out.println(count); 
     } 

    } 


}