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 a memoization based C++ trie solution which calculates the leaves of nodes only as a one off and stores the result in a variable in the node called "leaves". Unfortunately it doesn't pass all tests. Can someone point out a failing test case for it? Thanks in advance.
#include<map>#include<set>#include<list>#include<cmath>#include<ctime>#include<deque>#include<queue>#include<stack>#include<string>#include<bitset>#include<cstdio>#include<limits>#include<vector>#include<climits>#include<cstring>#include<cstdlib>#include<fstream>#include<numeric>#include<sstream>#include<iostream>#include<algorithm>#include<unordered_map>#define ALPHABET_SIZE 26#define CHAR_TO_INDEX(c) (c-'a')usingnamespacestd;classTrieNode{public:TrieNode*children[ALPHABET_SIZE];boolisLeaf;intleaves;//no. of leaves in trie rooted at this TrieNodeTrieNode(){for(inti=0;i<ALPHABET_SIZE;i++)children[i]=NULL;isLeaf=false;leaves=-1;//-1 means uncalculated}};classTrie{TrieNode*root;public:Trie(){root=newTrieNode();}voidadd(stringword){TrieNode*pCrawl=root;for(intlevel=0;level<word.length();level++){intindex=CHAR_TO_INDEX(word[level]);if(pCrawl->children[index]==NULL){cout<<"DEBUG: Creating node for '"<<word[level]<<"'\n";pCrawl->children[index]=newTrieNode();}pCrawl=pCrawl->children[index];}cout<<"DEBUG: Marking Leaf\n";pCrawl->isLeaf=true;}intcountLeaves(TrieNode*node){if(node->leaves!=-1)returnnode->leaves;intcount=0;if(node->isLeaf)count++;for(inti=0;i<ALPHABET_SIZE;i++){if(node->children[i])count+=countLeaves(node->children[i]);}node->leaves=count;returncount;}intfindCount(stringprefix){TrieNode*pCrawl=root;for(intlevel=0;level<prefix.length();level++){intindex=CHAR_TO_INDEX(prefix[level]);if(!pCrawl->children[index])return0;pCrawl=pCrawl->children[index];}returncountLeaves(pCrawl);}};intmain(){intn;cin>>n;TriemyTrie;for(inta0=0;a0<n;a0++){stringop;stringcontact;cin>>op>>contact;if(op=="add")myTrie.add(contact);elsecout<<myTrie.findCount(contact)<<endl;}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tries: Contacts
You are viewing a single comment's thread. Return to all comments →
I have a memoization based C++ trie solution which calculates the leaves of nodes only as a one off and stores the result in a variable in the node called "leaves". Unfortunately it doesn't pass all tests. Can someone point out a failing test case for it? Thanks in advance.