hackerrank-nodejs/trie.contacts.js at master · techiekats/hackerrank-nodejs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class TrieNode {
    constructor () {
        this.node = {};
        this.isTerminalNode = false;
        this.childrenCount = 0;
    }
    addString  = function (arr) {
        if (arr.length == 0) {
            this.isTerminalNode = true;
            this.childrenCount = 1;
        }
        else {
            let char = arr[0];
            //NOTE: because no duplicates. else this condition does not hold.
            this.childrenCount++;
            if (!this.node[char]) {
                this.node[char] = new TrieNode();
            }
            this.node[char].addString(arr.slice(1));
        }
    }
    deleteString = function (str) {
        //TODO
    }
    searchString = function (str) {
        //TODO
    }
    getPartialStringCount = function (str) {
        let char = str[0];
        if (!this.node[char])
        {
            return 0;
        }
        if (str.length == 1)
        {
            return this.node[char].childrenCount;
        }
        return this.node[char].getPartialStringCount(str.slice(1));
    }
}

let t = new TrieNode();
//NOTE: send the split up chars so that at each level of recursion do not have to split string
t.addString('khyati'.split(''));
console.assert(t.getPartialStringCount('kha'.split('')) == 0);
console.assert(t.getPartialStringCount('kh'.split('')) == 1);
t.addString('aarna'.split(''));
t.addString('aadhya'.split(''));
console.assert(t.getPartialStringCount('a'.split('')) == 2);
console.assert(t.getPartialStringCount('aa'.split('')) == 2);
console.assert(t.getPartialStringCount('aar'.split('')) == 1);
/*add hack
add hackerrank
find hac
find hak*/

t.addString('hack'.split(''));
t.addString('hackerrank'.split(''));
console.assert(t.getPartialStringCount('hac') == 2);
console.assert(t.getPartialStringCount('hak') == 0)

t.addString('z'.split(''));
console.assert(t.getPartialStringCount(['z']) == 1);
console.assert(t.getPartialStringCount(['t']) == 0);
console.assert(t.getPartialStringCount('khyati'.split('')) == 1);
console.assert(t.getPartialStringCount('khyatis'.split('')) == 0);