We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I have submitted the code for this question using Trie class in C#. My tests are timing out. I tried executing the test on my machine for test case #12. took 35091 milliseconds. Code added Below. Can someone please help to point out what am I missing. Thanks in Advance
public class Trie
{
TrieNode root;
private const int SIZE = 26;
public Trie()
{
root = new TrieNode(SIZE);
}
public void Add(string s)
{
TrieNode curNode = root;
int pos = 0;
for (int i = 0; i < s.Length; i++)
{
pos = s[i] - 'a';
if (curNode.Childern[pos] == null)
{
curNode.Childern[pos] = new TrieNode(SIZE);
}
curNode = curNode.Childern[pos];
if (i == s.Length - 1)
{
curNode.IsLeaf = true;
}
}
}
public int CountStringsWithPrefix(string prefix)
{
bool found = true;
TrieNode curNode = root;
int pos = 0;
for (int i = 0; (i < prefix.Length) && found; i++)
{
pos = prefix[i] - 'a';
if (curNode.Childern[pos] == null)
{
found = false;
}
curNode = curNode.Childern[pos];
}
return found ? CountLeaves(curNode) : 0;
}
private int CountLeaves(TrieNode node)
{
int count = 0;
if (node.IsLeaf) count++;
if (node.Childern != null)
{
for (int i = 0; i < 26; i++)
{
if (node.Childern[i] != null)
{
count += CountLeaves(node.Childern[i]);
}
}
}
return count;
}
}
public class TrieNode
{
TrieNode[] children;
public TrieNode(int size)
{
children = new TrieNode[size];
}
public TrieNode[] Childern { get { return children; } set { children = value; } }
public bool IsLeaf { get; set; }
};
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Contacts
You are viewing a single comment's thread. Return to all comments →
I have submitted the code for this question using Trie class in C#. My tests are timing out. I tried executing the test on my machine for test case #12. took 35091 milliseconds. Code added Below. Can someone please help to point out what am I missing. Thanks in Advance public class Trie { TrieNode root; private const int SIZE = 26;