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

  • spark4
     + 1 comment

    I am having issues getting my JS solution getting accepted as well, but am getting timeout errors on 3,4 & 7.

    Here is my code. Do you mind sharing what you did so that we can compare?

    function main() {
    var trie = {},
    	n = parseInt(readLine()),
        resp = '';
    
    for(var a0 = 0; a0 < n; a0++){
        var op_temp = readLine().split(' '),
            op = op_temp[0].trim(),
            contact = op_temp[1].trim();
        switch(op){
            case 'add':
                addName(contact, trie);
                break;
            case 'find':
                resp += (resp.length === 0) 
                    ? findPartial(contact, trie) 
                    : '\n'+findPartial(contact, trie);
                break;
            default:
            	break;
        }
    }
    
    console.log(resp);
    return;
}
    
    
function addName(name, trie){
    var tree = trie;
    for(var i = 0; i < name.length; i ++){
        if(!tree[name[i]]) tree[name[i]] = {};
        tree = tree[name[i]];
        if(i === name.length - 1 && !tree["*"]) tree["*"] = "*";
    }
    return;
}


function findPartial(partial, trie){
    var prefixTree = trie,
        numPartials = 0;
    for(var i = 0; i < partial.length; i ++){
        if(prefixTree[partial[i]]) prefixTree = prefixTree[partial[i]];
        else return numPartials;
    }
    var stack = [prefixTree];
    while(stack.length > 0){
        var currTree = stack.pop();
        for(var letter in currTree){
            if(letter === "*") numPartials++;
            else stack.push(currTree[letter]);
        }
    }
    return numPartials;
}