시도 횟수 - 연락처 - Hackerrank

Question

나는 현재 hackerrank Tries - Contacts

에이 문제를 해결하기 위해 노력하고 그리고 내 알고리즘은 하나의 테스트 케이스 실패합니다. 테스트 케이스 # 1. 이 테스트 케이스를 통과하기 위해 내가 바꿀 필요가있는 것을 통찰력을 공유 할 수 있습니까? 그 자식 노드의 해시 맵을 포함하는 TrieNode 클래스를 사용하고 있습니다. 또한 각 노드의 크기를 저장하여 얼마나 많은 단어가 들어 있는지를 결정합니다. 다음과 같이

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

코드는 다음과 같습니다 : 다음과 같이

테스트 케이스 # 1은

마지막 하나를 제외한 모든 노드의 개수가 증가하여 트리는에 단어를 추가

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

.

current.size++; 

에 코드를 통과 시험 :이 종류의 (루프 후) addWord 방법의 끝에서 다시 한 번이 줄을 추가 오프별로 한 https://en.wikipedia.org/wiki/Off-by-one_error

호출 된 오차 발견하는 것은 매우 일반적이고 어렵다 경우 0 코드에서이 특정 버그는 HAC-kerrank 같은 접두사를 볼 때 표시되지 않습니다,하지만 당신은 hackerran K 같은 마지막 문자를 포함한 전체 단어를 찾아 볼 때 표시 않기 때문에 또는 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); 
     } 

    } 


}