Hacker Rank: Counting names with prefix matches using a trie











up vote
2
down vote

favorite












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

}
}









share|improve this question




























    up vote
    2
    down vote

    favorite












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

    }
    }









    share|improve this question


























      up vote
      2
      down vote

      favorite









      up vote
      2
      down vote

      favorite











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

      }
      }









      share|improve this 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;
      }
      }

      }
      }






      c# performance programming-challenge trie






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Nov 18 at 7:15









      t3chb0t

      33.7k744108




      33.7k744108










      asked Nov 18 at 1:12









      Luke Xu

      1556




      1556






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          2
          down vote













          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.






          share|improve this answer




























            up vote
            2
            down vote













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






            share|improve this answer























            • Smart solution!
              – Henrik Hansen
              Nov 19 at 20:38











            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "196"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














             

            draft saved


            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207888%2fhacker-rank-counting-names-with-prefix-matches-using-a-trie%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            2
            down vote













            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.






            share|improve this answer

























              up vote
              2
              down vote













              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.






              share|improve this answer























                up vote
                2
                down vote










                up vote
                2
                down vote









                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.






                share|improve this answer












                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.







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered Nov 18 at 1:48









                1201ProgramAlarm

                2,9552821




                2,9552821
























                    up vote
                    2
                    down vote













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






                    share|improve this answer























                    • Smart solution!
                      – Henrik Hansen
                      Nov 19 at 20:38















                    up vote
                    2
                    down vote













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






                    share|improve this answer























                    • Smart solution!
                      – Henrik Hansen
                      Nov 19 at 20:38













                    up vote
                    2
                    down vote










                    up vote
                    2
                    down vote









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






                    share|improve this answer














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







                    share|improve this answer














                    share|improve this answer



                    share|improve this answer








                    edited Nov 19 at 20:34

























                    answered Nov 19 at 19:02









                    tinstaafl

                    6,320727




                    6,320727












                    • Smart solution!
                      – Henrik Hansen
                      Nov 19 at 20:38


















                    • Smart solution!
                      – Henrik Hansen
                      Nov 19 at 20:38
















                    Smart solution!
                    – Henrik Hansen
                    Nov 19 at 20:38




                    Smart solution!
                    – Henrik Hansen
                    Nov 19 at 20:38


















                     

                    draft saved


                    draft discarded



















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207888%2fhacker-rank-counting-names-with-prefix-matches-using-a-trie%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Сан-Квентин

                    Алькесар

                    Josef Freinademetz