Krdytkyu

Practicing hacker rank questions and would love some feedback on how I could perform optimizations on a Trie.

This code will add a bunch of names into a trie and then when asked will turn how many names belong to a partial match. eg.

jenn, jennifer, george, jenny



partial => jen

return => 3

using System;

using System.Collections.Generic;

using System.IO;



namespace ConsoleApplication1

{

    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

    {

        private readonly Trie _trieArray = new Trie[26];

        private int _findCount = 0;

        private bool _data = false;

        private char _name;

        private int _occurances = 0;



        public void add(string s)

        {

            s = s.ToLower();

            add(s, this);

        }



        private void add(string s, Trie t)

        {

            char first = Char.Parse(s[0].ToString());

            int index = first - 'a';



            if (t._trieArray[index] == null)

            {

                t._trieArray[index] = new Trie {_name = first};

            }



            if (s.Length > 1)

            {

                add(s.Substring(1), t._trieArray[index]);

            }

            else

            {

                t._trieArray[index]._data = true;

            }



            t._trieArray[index]._occurances++;

        }



        public int find(string s)

        {

            s = s.ToLower();

            find(s, this);



            int 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[0].ToString());

                int index = first - 'a';

                find(s.Substring(1), t._trieArray[index]);

            }

            else

            {

                _findCount = t._occurances;

            }

        }



    }

}

You don't validate your input. If the user enters a string with no space in it, you'll get an exception.

s[0] is a character, so why do you convert it to a string to convert it back to a character?

You should avoid allocating _trieArray until you need it. Otherwise you'll allocate a bunch of memory you don't use (in all your leaf nodes).

You don't need to use _findCount. Your private find method can just return that value.

As an additional exercise, rewrite add to not be recursive, and avoid making all those (sub)string copies.

Some additional points:

To me it is easier to deal with if you separate the Trie from it's nodes. To this end a Node class would help.

Instead of using an array, I think you can get better performance by using a Dictionary<char,Node> to hold the children of each node.

Using a separate Node class gives you the option to optimize your prefix count by keeping a count of each word that has the prefix up to that point.

A Trie class with a Node class using a Dictionary could look something like this:

class Trie

{

    private class Node

    {

        public char value = '';

        public int wordCount = 0;

        //public Node parent = null; for future use

        public Dictionary<char, Node> children = new Dictionary<char, Node>();



        public Node() { }

        public Node(char value)

        {

            this.value = value;

        }

        public Node AddChild(char value)

        {

            Node temp = new Node();

            if (!children.TryGetValue(value,out temp))

            {

                temp = new Node();

                children.Add(value, temp);

                //children[value].parent = this;

            }

            temp.wordCount++;

            return temp;

        }

    }

    private readonly Node root = new Node();



    public Trie() { }



    public void AddWord(string word)

    {

        Node temp = root;

        foreach (char c in word)

        {

            temp = temp.AddChild(c);                

        }

    }

    public int prefixCount(string prefix)

    {

        Node temp = root;

        foreach (char c in prefix)

        {

            if (!temp.children.TryGetValue(c,out temp))

            {

                return 0;

            }

        }

        return temp.wordCount;

    }



}

A solution could look like this:

public static void RunSolution(TextReader sin,TextWriter sout )

{

    int lines = int.Parse(sin.ReadLine());

    Trie contacts = new Trie();

    for(int line = 0; line < lines; ++line)

    {

        var instructions = sin.ReadLine().Split(' ');

        switch(instructions[0])

        {

            case "add":

                {

                    contacts.AddWord(instructions[1]);

                    break;

                }

            case "find":

                {

                    sout.WriteLine(contacts.prefixCount(instructions[1]));

                    break;

                }

            default:

                {

                    throw new InvalidDataException("no op code");

                }

        }

    }

}

With this all Trie operations become O(n) the length of the string, since any lookups are close to O(1).