尝试 - 联系人 - 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

向Trie添加单词时，除最后一个节点外，所有节点的计数都会增加。这是非常常见的，很难注意到一种错误称为https://en.wikipedia.org/wiki/Off-by-one_error

在addWord方法结束时再次添加此行（在循环之后）：

current.size++;

您的代码通过了测试用例0，因为当您查找hac-kerrank之类的前缀时，代码中的这个特定错误不会显示，但是当您查找完整的单词（包括最后一个字符，如hackerrank或sssss）时，它会显示

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

    }


}

Answer 3

如果你要结帐：enter link description here

并且还使用他们的测试用例：4添加hack添加hackerrank找到hac find hak

它会编译。

//来自他在https://github.com/RodneyShag/HackerRank_solutions/blob/master/Data%20Structures/Trie/Contacts/Solution.java的网站

import java.util.Scanner;
import java.util.HashMap;
public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Trie trie = new Trie();
        for (int i = 0; i < n; i++) {
            String operation = scan.next();
            String contact   = scan.next();
            if (operation.equals("add")) {
                trie.add(contact);
            } else if (operation.equals("find")) {
                System.out.println(trie.find(contact));
            }
        }
        scan.close();
    }
}
/* Based loosely on tutorial video in this problem */
class TrieNode {
    private HashMap<Character, TrieNode> children = new HashMap<>();
    public int size = 0; // this was the main trick to decrease runtime to pass tests.
    public void putChildIfAbsent(char ch) {
        children.putIfAbsent(ch, new TrieNode());
    }
    public TrieNode getChild(char ch) {
        return children.get(ch);
    }
}
class Trie {
    TrieNode root = new TrieNode();
    Trie(){} // default constructor

    Trie(String[] words) {
        for (String word : words) {
            add(word);
        }
    }

    public void add(String str) {
        TrieNode curr = root;
        for (int i = 0; i < str.length(); i++) {
            Character ch = str.charAt(i);
            curr.putChildIfAbsent(ch);
            curr = curr.getChild(ch);
            curr.size++;
        }
    }

    public int find(String prefix) {
        TrieNode curr = root;

        /* Traverse down tree to end of our prefix */
        for (int i = 0; i < prefix.length(); i++) {
            Character ch = prefix.charAt(i);
            curr = curr.getChild(ch);
            if (curr == null) {
                return 0;
            }
        }
        return curr.size;
    }
}