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).

• user73941: Smart solution!