How can I make my trie more efficient?

Question

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

Vassaux

Try not using recursion, you are creating too many strings when it is not needed, use index to get 1 char from string instead of substring – Flyaway

Yeah, I know there's the iterative approach but I feel like since this is a "tree like" structure recursion would be some what appropriate. I feel like I'm definitely missing something else asides from recursion though. I'll give the substring method a try though! Would you suggest I try "StringBuilder"? – Vassaux

To get first char you can use s[0]. Since you are going only one path in tree there is no need for recursion and then you would not need to use substring. Even with recursion if u passed down the index of character inside the string not the substring it might be faster. – Flyaway

Hmmm, okay thanks. Gonna give that a try. – Vassaux

Unless there is a specific question, this question is probably better suited for a Code Review at: codereview.stackexchange.com "how to improve the efficiency..." is rather vague; what are the current bottlenecks? have you profiled? etc... – Eyepiece

@MetroSmurf Thanks for the advice. What do you mean by "profiled"? – Vassaux

@MetroSmurf Oh wow never new about profiling... Do you have any suggestions for C# profilers that you would recommend? – Vassaux

Answer 1

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)

Noletta

Maybe I'm not understanding but I don't see how weighted trees will help me. Your method is still going to require all traversals of the tree am I right? For example, you have "help" and "hello" and say we do find("hel"). Your method is going to traverse to p and then l -> o. – Vassaux

When adding words, increase the count of every charachternode you pass. When you look for hel it stops at the l and returns the count of that node. – Noletta

Thats why i love the algorithm/ data structures section, solutions are usually way more simple than expected. – Noletta

Yeah, same here. I totally agree with you. – Vassaux

Answer 2

I think, this link must be very helpfull

There, you can find the good implementation of a trie data structure, but it's a java implementation. I implemented trie on c# with that great article one year ago, and i tried to find solution to an another hackerrank task too ) It was successful.

In my task, i had to a simply trie (i mean my alphabet equals 2) and only one method for adding new nodes:

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

Korykorzybski

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – Ansate

@DavidMedenjak i've added some more info – Korykorzybski

Please remove the Sourcecode since this is a programming challenge and not a real world problem. – Noletta

sorry, but why i have to remove my source code ? it's against stackoverflow's rules? Futhermore the code above is a small part of the whole solution of one unnamed hacker rank task. – Korykorzybski