Jak sprawić, by mój triest był bardziej wydajny?

Question

Pracuję nad problemem z hakerem i I wierzę, moje rozwiązanie jest poprawne. Jednak większość moich przypadków testowych jest limitowana. Czy ktoś może sugerować, jak poprawić wydajność mojego kodu?

Ważna część kodu rozpoczyna się od "Klasy Trie".

Dokładna pytanie można znaleźć tutaj: 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++; 
      } 
     } 
    } 

} 

EDIT: Zrobiłem pewne sugestie w komentarzach, ale uświadomiłem sobie, że nie może zastąpić s.Substring (1) ze s [0] ... ponieważ potrzebuję s [1..n]. AND s [0] zwraca znak, więc i tak będę musiał to zrobić .ToString.

Ponadto, aby dodać trochę więcej informacji. Chodzi o to, że musi zliczyć WSZYSTKIE nazwiska po prefiksie na przykład.

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

Answer 1

Mogę po prostu napisać rozwiązanie, które daje ci 40 punktów, ale myślę, że to nie będzie dobra zabawa.

• użycie Marka wyliczający <char> zamiast jakichkolwiek operacji strun
• Hrabia podczas dodawania wartości
• dowolny minus charachter 'a' sprawia dobre arrayindex (daje wartości między 0 a 25)

Answer 2

myślę, this link musi być bardzo pomocny

Tam można znaleźć dobre wdrożenie struktury danych Trie, ale jest to implementacja Java. W ubiegłym roku zaimplementowałam TRIE na C# z tym świetnym artykułem i próbowałem znaleźć rozwiązanie dla innego zadania hackerrank). Udało się.

Moim zadaniem, musiałem Jest po prostu trie (mam na myśli mój alfabet równa 2) i tylko jedną metodę dodawania nowych węzłów:

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