-
Notifications
You must be signed in to change notification settings - Fork 40
/
ImplementTrie(PrefixTree).js
79 lines (73 loc) · 2.27 KB
/
ImplementTrie(PrefixTree).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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Source : https://leetcode.com/problems/implement-trie-prefix-tree
// Author : Dean Shi
// Date : 2022-01-07
/***************************************************************************************
* A trie (pronounced as "try") or prefix tree is a tree data structure used to
* efficiently store and retrieve keys in a dataset of strings. There are various
* applications of this data structure, such as autocomplete and spellchecker.
*
* Implement the Trie class:
*
* Trie() Initializes the trie object.
* void insert(String word) Inserts the string word into the trie.
* boolean search(String word) Returns true if the string word is in the trie (i.e.,
* was inserted before), and false otherwise.
* boolean startsWith(String prefix) Returns true if there is a previously inserted
* string word that has the prefix prefix, and false otherwise.
*
* Example 1:
*
* Input
* ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
* [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
* Output
* [null, null, true, false, true, null, true]
*
* Explanation
* Trie trie = new Trie();
* trie.insert("apple");
* trie.search("apple"); // return True
* trie.search("app"); // return False
* trie.startsWith("app"); // return True
* trie.insert("app");
* trie.search("app"); // return True
*
* Constraints:
*
* 1 <= word.length, prefix.length <= 2000
* word and prefix consist only of lowercase English letters.
* At most 3 * 104 calls in total will be made to insert, search, and startsWith.
*
*
***************************************************************************************/
var Trie = function() {
this.store = []
};
/**
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
this.store.push(word)
};
/**
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
return this.storeSet.has(word)
};
/**
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
return this.store.some((word) => word.startsWith(prefix))
};
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/