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.
  1. Tries: Contacts
  2. Discussions

Tries: Contacts

  • chandniverma
     + 1 comment

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

using namespace std;

class TrieNode {
    public:
    TrieNode *children[ALPHABET_SIZE];
    bool isLeaf;
    int leaves;//no. of leaves in trie rooted at this TrieNode

    TrieNode (){
        for (int i=0; i<ALPHABET_SIZE; i++)
            children[i] = NULL;
        isLeaf = false;
	leaves = -1;//-1 means uncalculated
    }
};

class Trie {
    TrieNode *root;

    public:
    Trie (){
        root = new TrieNode();
    }

    void add(string word){
        TrieNode *pCrawl = root;

        for (int level=0; level<word.length(); level++){
            int index = CHAR_TO_INDEX(word[level]);
            if (pCrawl->children[index] == NULL) {
		cout<<"DEBUG: Creating node for '"<<word[level]<<"'\n";
                pCrawl->children[index] = new TrieNode();
	    }
            pCrawl = pCrawl->children[index];
        }

	cout<<"DEBUG: Marking Leaf\n";
        pCrawl->isLeaf = true;
    }

    int countLeaves (TrieNode *node){
	if (node->leaves != -1)
	    return node->leaves;

        int count = 0;
        if (node->isLeaf)
            count++;

        for (int i=0; i<ALPHABET_SIZE; i++){
            if (node->children[i])
                count+=countLeaves(node->children[i]);
        }

	node->leaves = count;
        return count;
    }

    int findCount(string prefix){
        TrieNode *pCrawl = root;

        for (int level=0; level<prefix.length(); level++){
            int index = CHAR_TO_INDEX(prefix[level]);
            if (!pCrawl->children[index])
                return 0;
            pCrawl = pCrawl->children[index];
        }

        return countLeaves(pCrawl);
    }
};

int main(){
    int n;
    cin >> n;
    Trie myTrie;
    for(int a0 = 0; a0 < n; a0++){
        string op;
        string contact;
        cin >> op >> contact;
        if (op == "add")
            myTrie.add(contact);
        else
            cout<<myTrie.findCount(contact)<<endl;
    }
    return 0;
}