Hacker Rank: Counting names with prefix matches using a trie

Question

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

    }
}

Answer 1

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.

Answer 2

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 = '\0';
        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).