如何让我的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]返回一个char,所以无论如何我都需要做.ToString.

另外,添加更多信息.这个想法是它需要在前缀之后计算所有名称,例如.

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

Answer 1

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

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