嘗試次數 - 聯繫方式 - 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

當您添加的話你的特里，你增量次數的所有節點，除了最後一個。這是很常見的，很難注意到樣的錯誤被取消接一個https://en.wikipedia.org/wiki/Off-by-one_error

再次在addWord方法結束（循環後）加入這一行：

current.size++; 

你的代碼通過測試0的情況下，因爲在你的代碼這個特殊的錯誤不會顯示出來，當你看像HAC-kerrank的前綴，但確實顯示了，當你仰望爲完整的單詞，包括像hackerran ķ的最後字符或SSSS 小號

Answer 2

我有這樣的解決方案，除了測試用例0,1 & 5個所有其它超時。這裏是我在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); 
     } 

    } 


}