我怎样才能让我的 trie 更有效率？

Question

我正在研究黑客排名问题，我相信我的解决方案是正确的。但是，我的大多数测试用例都已超时。有人可以建议如何提高我的代码效率吗？

代码的重要部分从 "Trie Class" 开始。

可以在这里找到确切的问题：https://www.hackerrank.com/challenges/contacts

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    static void Main(String[] args)
    {
        int N = Int32.Parse(Console.ReadLine());
        string[,] argList = new string[N, 2];
        for (int i = 0; i < N; i++)
        {
            string[] s = Console.ReadLine().Split();
            argList[i, 0] = s[0];
            argList[i, 1] = s[1];
        }

        Trie trie = new Trie();

        for (int i = 0; i < N; i++)
        {
            switch (argList[i, 0])
            {
                case "add":
                    trie.add(argList[i, 1]);
                    break;
                case "find":
                    Console.WriteLine(trie.find(argList[i, 1]));
                    break;
                default:
                    break;
            }
        }
    }
}

class Trie
{
    Trie[] trieArray = new Trie[26];
    private int findCount = 0;
    private bool data = false;
    private char name;

    public void add(string s)
    {
        s = s.ToLower();
        add(s, this);
    }

    private void add(string s, Trie t)
    {
        char first = Char.Parse(s.Substring(0, 1));
        int index = first - 'a';

        if(t.trieArray[index] == null)
        {
            t.trieArray[index] = new Trie();
            t.trieArray[index].name = first;
        }

        if (s.Length > 1)
        {
            add(s.Substring(1), t.trieArray[index]);
        }
        else
        {
            t.trieArray[index].data = true;
        }
    }

    public int find(string s)
    {
        int ans;
        s = s.ToLower();
        find(s, this);

        ans = findCount;
        findCount = 0;
        return ans;
    }

    private void find(string s, Trie t)
    {
        if (t == null)
        {
            return;
        }
        if (s.Length > 0)
        {
            char first = Char.Parse(s.Substring(0, 1));
            int index = first - 'a';
            find(s.Substring(1), t.trieArray[index]);
        }
        else
        {
            for(int i = 0; i < 26; i++)
            {
                if (t.trieArray[i] != null)
                {
                    find("", t.trieArray[i]);
                }
            }

            if (t.data == true)
            {
                findCount++;
            }
        }
    }

}

编辑： 我在评论中提出了一些建议，但意识到我无法用 s[0] 替换 s.Substring(1)... 因为我实际上需要 s[1..n]。 AND s[0] returns 一个字符，所以无论如何我都需要在它上面做 .ToString。

另外，再补充一点信息。这个想法是它需要计算前缀后的所有名称。

Input: "He"
Trie Contains:
"Hello"
"Help"
"Heart"
"Ha"
"No"
Output: 3

Answer 1

我可以在这里 post 一个给你 40 分的解决方案，但我想这不会有任何乐趣。

使用 Enumerator 而不是任何字符串操作
边加值边计数
任何减去 'a' 的字符都是一个很好的数组索引（给你 0 到 25 之间的值）

Answer 2

我想，this link一定很有帮助

在那里，您可以找到 trie 数据结构的良好实现，但它是 java 实现。一年前我用那篇很棒的文章在 c# 上实现了 trie，我也试图找到另一个 hackerrank 任务的解决方案）它成功了。

在我的任务中，我不得不简单地尝试一下（我的意思是我的字母表等于 2）并且只有一种添加新节点的方法：

public class Trie
{
   //for integer representation in binary system 2^32
    public static readonly int MaxLengthOfBits = 32;
    //alphabet trie size
    public static readonly int N = 2;

    class Node
    {
        public Node[] next = new Node[Trie.N];
    }

    private Node _root;
}

public void AddValue(bool[] binaryNumber)
{
    _root = AddValue(_root, binaryNumber, 0);
}

private Node AddValue(Node node, bool[] val, int d)
{
    if (node == null) node = new Node();

    //if least sagnificient bit has been added
    //need return
    if (d == val.Length)
    {   
        return node;
    }

    // get 0 or 1 index of next array(length 2)
    int index = Convert.ToInt32(val[d]); 
    node.next[index] = AddValue(node.next[index], val, ++d);
    return node;
}

我怎样才能让我的 trie 更有效率？

How can I make my trie more efficient?

c#

data-structures

trie