Essais - Contacts - HackerRank

Question

Je suis actuellement tentent de résoudre ce problème sur HackerRank Tries - Contacts

Et mon algorithme échoue pour un seul cas de test. Cas de test n ° 1 Quelqu'un peut-il partager un aperçu de ce que j'ai besoin de changer afin de passer ce test. J'utilise une classe TrieNode qui contient un hashmap de ses nœuds enfants. Je stocke également la taille de chaque noeud pour définir le nombre de mots qu'il contient.

cas d'essai n ° 1 est la suivante:

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

Le code est le suivant:

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

Lorsque vous ajoutez des mots à votre Trie vous incrémenter compte pour tous les nœuds, sauf le dernier . Ceci est assez fréquent et difficile à remarquer type d'erreur appelé hors par un https://en.wikipedia.org/wiki/Off-by-one_error

ajouter cette ligne une fois de plus à la fin de la méthode addword (après la boucle):

current.size++; 

Votre code passé le test 0 cas parce que ce bogue particulier dans votre code ne montre pas quand vous regardez un préfixe comme hac-kerrank, mais ne montre quand vous regardez pour mot complet, y compris le dernier caractère comme hackerran k ou de s

Answer 2

J'ai cette solution, sauf cas de test 0, 1 & 5 tous les autres sont hors délai. Voici ma mise en œuvre dans Java 8. Où dois-je améliorer mon code pour passer tous les cas de test

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); 
     } 

    } 


}