尝试 - 联系人 - Hackerrank

Question

我目前正在尝试在 hackerrank 上解决这个挑战 Tries - Contacts

而且我的算法仅对一个测试用例失败。测试用例#1。任何人都可以分享任何关于我需要改变什么才能通过这个测试用例的见解吗？我正在使用包含其子节点的哈希图的 TrieNode class。我还存储了每个节点的大小以表示它包含多少个单词。

测试用例#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 中添加单词时，您会增加所有节点的计数，最后一个节点除外。这是一种很常见且很难注意到的错误，称为 off-by-one https://en.wikipedia.org/wiki/Off-by-one_error

在 addWord 方法的末尾再次添加这一行（在循环之后）：

current.size++;

您的代码通过了测试用例 0，因为当您查找像 hac-kerrank 这样的前缀时，您代码中的这个特定错误不会出现，但会在您查找时出现查找包含 last 字符的完整单词，如 hackerrank 或 ssss s

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个添加黑客添加黑客等级找哈克找到 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;
    }
}

尝试 - 联系人 - Hackerrank

Tries - Contacts - Hackerrank

java

algorithm

prefix

data-structures