Làm thế nào tôi có thể làm cho trie của tôi hiệu quả hơn?

Question

Tôi đang làm việc về vấn đề xếp hạng của hacker và tôi tin giải pháp của tôi là chính xác. Tuy nhiên, hầu hết các trường hợp thử nghiệm của tôi đang hết thời gian chờ. Có thể một số đề nghị làm thế nào để cải thiện hiệu quả của mã của tôi?

Phần quan trọng của mã bắt đầu tại "Lớp Trie".

Câu hỏi chính xác có thể được tìm thấy ở đây: 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: tôi đã làm một số gợi ý trong các ý kiến ​​nhưng nhận ra rằng tôi không thể thay thế s.Substring (1) với s [0] ... bởi vì tôi thực sự cần s [1.n]. AND s [0] trả về một char vì vậy tôi sẽ cần phải làm. ToString trên nó anyways.

Ngoài ra, để thêm một chút thông tin. Ý tưởng là nó cần phải đếm TẤT CẢ các tên sau một tiền tố ví dụ.

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

Answer 1

Tôi chỉ có thể đăng một giải pháp ở đây cung cấp cho bạn 40 điểm nhưng tôi đoán điều này sẽ không vui.

• Make sử dụng Enumerator <char> thay vì bất kỳ hoạt động chuỗi
• Đếm khi thêm giá trị
• bất kỳ charachter trừ 'a' làm một arrayindex tốt (cung cấp cho bạn các giá trị giữa 0 và 25)

Answer 2

tôi nghĩ rằng, this link phải rất hữu ích

Ở đó, bạn có thể tìm thấy việc triển khai tốt cấu trúc dữ liệu trie, nhưng đó là triển khai java. Tôi thực hiện trie trên C# với bài viết tuyệt vời một năm trước đây, và tôi đã cố gắng tìm giải pháp cho một nhiệm vụ hackerrank khác quá) Nó đã thành công.

Trong nhiệm vụ của tôi, tôi đã phải một cách đơn giản Trie (i có nghĩa là bảng chữ cái của tôi bằng 2) và chỉ có một phương pháp để thêm các nút mới:

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