/
Implement Trie (Prefix Tree).js
65 lines (61 loc) · 1.44 KB
/
Implement Trie (Prefix Tree).js
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
/**
* @constructor
* Initialize your data structure here.
*/
var TrieNode = function() {
var obj = new Object();
obj.end = false;
obj.nexts = {};
return obj;
};
var Trie = function() {
this.root = TrieNode();
};
/**
* @param {string} word
* @return {void}
* Inserts a word into the trie.
*/
Trie.prototype.insert = function(word) {
var cur = this.root;
for(var i = 0; i < word.length; i++){
if(!(word[i] in cur.nexts)){
cur.nexts[word[i]] = TrieNode();
}
cur = cur.nexts[word[i]];
}
cur.end = true;
};
/**
* @param {string} word
* @return {boolean}
* Returns if the word is in the trie.
*/
Trie.prototype.search = function(word) {
var cur = this.root;
for(var i = 0 ; i < word.length; i++){
if(!cur || !cur.nexts || !(word[i] in cur.nexts)){return false;}
cur = cur.nexts[word[i]];
}
return cur.end === true;
};
/**
* @param {string} prefix
* @return {boolean}
* Returns if there is any word in the trie
* that starts with the given prefix.
*/
Trie.prototype.startsWith = function(prefix) {
var cur = this.root;
for(var i = 0 ; i < prefix.length; i++){
if(!cur || !cur.nexts || !(prefix[i] in cur.nexts)){return false;}
cur = cur.nexts[prefix[i]];
}
return true;
};
/**
* Your Trie object will be instantiated and called as such:
* var trie = new Trie();
* trie.insert("somestring");
* trie.search("key");
*/