-
Notifications
You must be signed in to change notification settings - Fork 236
/
trie.js
68 lines (57 loc) · 1.45 KB
/
trie.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
const {
END_WORD_SYMBOL,
validate,
getLastLetterNode,
tryDelete,
} = require('./trieUtil');
class Trie {
constructor() {
this.head = {};
}
sortTrie(node, word, sorted) {
if (END_WORD_SYMBOL in node) {
sorted.push(word);
}
// this call skips Symbols
const letters = Object.keys(node);
letters.forEach((letter) => {
this.sortTrie(node[letter], word + letter, sorted);
});
}
add(word, value = word) {
validate(word);
if (value === undefined || value === null) {
throw new Error('The given value is invalid.');
}
// this returns a pointer to the last value
const current = getLastLetterNode(this.head, word, true);
current[END_WORD_SYMBOL] = value;
}
hasWord(word) {
validate(word);
const retValue = getLastLetterNode(this.head, word);
// Only return true is whole word was found
return !!retValue.value && !retValue.isSubstring;
}
getValue(word) {
validate(word);
const retValue = getLastLetterNode(this.head, word);
return retValue.value;
}
// this returns the longest prefix
getPrefix(word) {
validate(word);
const retValue = getLastLetterNode(this.head, word);
return !!retValue.value && retValue.word;
}
remove(wordToRemove) {
validate(wordToRemove);
tryDelete(wordToRemove, -1, this.head);
}
sort() {
const sorted = [];
this.sortTrie(this.head, '', sorted);
return sorted;
}
}
module.exports = Trie;