How can I make my trie more efficient?

Luke Xu

I'm working on a hacker rank problem and I believe my solution is correct. However, most of my test cases are being timed out. Could some one suggest how to improve the efficiency of my code?

The important part of the code starts at the "Trie Class".

The exact question can be found here: 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: I did some suggestions in the comments but realized that I can't replace s.Substring(1) with s[0]... because I actually need s[1..n]. AND s[0] returns a char so I'm going to need to do .ToString on it anyways.

Also, to add a little more information. The idea is that it needs to count ALL names after a prefix for example.

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

I could just post a solution here that gives you 40 points but i guess this wont be any fun.

  • Make use of Enumerator<char> instead of any string operations
  • Count while adding values
  • any charachter minus 'a' makes a good arrayindex (gives you values between 0 and 25)

enter image description here

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集
0

コメントを追加

0

関連記事

分類Dev

How can I make a recursive search for longest node more efficient?

分類Dev

How can I make a code more efficient and shorter?

分類Dev

How can i make my database method more future proof?

分類Dev

How can I write the following code in a more efficient and pythonic way?

分類Dev

How can I make the button more visible?

分類Dev

How can I make Elixir mix test output more verbose?

分類Dev

How can I make Elixir mix test output more verbose?

分類Dev

How can I make a switch statement more object oriented?

分類Dev

How can I make Emacs scroll horizontally more smoothly?

分類Dev

How can I make WiFi more stable on Ubuntu 15.10?

分類Dev

How can I create more colors for my plot?

分類Dev

How can I use interfaces to allow for more than 1 struct type to make code more useable?

分類Dev

How to make multiple includes more efficient with EF Core 3.0

分類Dev

How can I make my glob work for cogs on Linux

分類Dev

How can I make a table inside my shiny box with RandomIcon()

分類Dev

How can I make a triangle drawable on the top left of my view?

分類Dev

How can I make my button call a rotation of GIFs?

分類Dev

How can I make my sprite not go crosswise in pygame?

分類Dev

How can I make my div's appear in a horizontal way?

分類Dev

How can I make the pixel value of the height in my code dynamic?

分類Dev

How can I make my bot delete its own message?

分類Dev

My Prestashop is slow - how can I make it faster?

分類Dev

Is there any ways to make this more efficient?

分類Dev

Make string checker more efficient

分類Dev

How can I make Ubuntu not lock my screen when I close my laptop?

分類Dev

Discord.py: How can I make a command that i can only do with my user ID?

分類Dev

How can I adapt this .autocomplete to make it work with more than one word?

分類Dev

How do I make it so that a user can not post more than one message in a row, discord.js

分類Dev

How can I make this function more modular and be used for multiple members of a struct?

Related 関連記事

  1. 1

    How can I make a recursive search for longest node more efficient?

  2. 2

    How can I make a code more efficient and shorter?

  3. 3

    How can i make my database method more future proof?

  4. 4

    How can I write the following code in a more efficient and pythonic way?

  5. 5

    How can I make the button more visible?

  6. 6

    How can I make Elixir mix test output more verbose?

  7. 7

    How can I make Elixir mix test output more verbose?

  8. 8

    How can I make a switch statement more object oriented?

  9. 9

    How can I make Emacs scroll horizontally more smoothly?

  10. 10

    How can I make WiFi more stable on Ubuntu 15.10?

  11. 11

    How can I create more colors for my plot?

  12. 12

    How can I use interfaces to allow for more than 1 struct type to make code more useable?

  13. 13

    How to make multiple includes more efficient with EF Core 3.0

  14. 14

    How can I make my glob work for cogs on Linux

  15. 15

    How can I make a table inside my shiny box with RandomIcon()

  16. 16

    How can I make a triangle drawable on the top left of my view?

  17. 17

    How can I make my button call a rotation of GIFs?

  18. 18

    How can I make my sprite not go crosswise in pygame?

  19. 19

    How can I make my div's appear in a horizontal way?

  20. 20

    How can I make the pixel value of the height in my code dynamic?

  21. 21

    How can I make my bot delete its own message?

  22. 22

    My Prestashop is slow - how can I make it faster?

  23. 23

    Is there any ways to make this more efficient?

  24. 24

    Make string checker more efficient

  25. 25

    How can I make Ubuntu not lock my screen when I close my laptop?

  26. 26

    Discord.py: How can I make a command that i can only do with my user ID?

  27. 27

    How can I adapt this .autocomplete to make it work with more than one word?

  28. 28

    How do I make it so that a user can not post more than one message in a row, discord.js

  29. 29

    How can I make this function more modular and be used for multiple members of a struct?

ホットタグ

アーカイブ