-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
Trie.js
132 lines (119 loc) · 3.35 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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
class TrieNode {
constructor(key, parent) {
this.key = key
this.count = 0
this.children = Object.create(null)
if (parent === undefined) {
this.parent = null
} else {
this.parent = parent
}
}
}
class Trie {
constructor() {
// create only root with null key and parent
this.root = new TrieNode(null, null)
}
// Recursively finds the occurrence of all words in a given node
static findAllWords(root, word, output) {
if (root === null) return
if (root.count > 0) {
if (typeof output === 'object') {
output.push({ word, count: root.count })
}
}
let key
for (key in root.children) {
word += key
this.findAllWords(root.children[key], word, output)
word = word.slice(0, -1)
}
}
insert(word) {
if (typeof word !== 'string') return
if (word === '') {
this.root.count += 1
return
}
let node = this.root
const len = word.length
let i
for (i = 0; i < len; i++) {
if (node.children[word.charAt(i)] === undefined) {
node.children[word.charAt(i)] = new TrieNode(word.charAt(i), node)
}
node = node.children[word.charAt(i)]
}
node.count += 1
}
findPrefix(word) {
if (typeof word !== 'string') return null
let node = this.root
const len = word.length
let i
// After end of this loop node will be at desired prefix
for (i = 0; i < len; i++) {
if (node.children[word.charAt(i)] === undefined) return null // No such prefix exists
node = node.children[word.charAt(i)]
}
return node
}
remove(word, count) {
if (typeof word !== 'string') return
if (typeof count !== 'number') count = 1
else if (count <= 0) return
// for empty string just delete count of root
if (word === '') {
if (this.root.count >= count) this.root.count -= count
else this.root.count = 0
return
}
let child = this.root
const len = word.length
let i, key
// child: node which is to be deleted
for (i = 0; i < len; i++) {
key = word.charAt(i)
if (child.children[key] === undefined) return
child = child.children[key]
}
// Delete no of occurrences specified
if (child.count >= count) child.count -= count
else child.count = 0
// If some occurrences are left we don't delete it or else
// if the object forms some other objects prefix we don't delete it
// For checking an empty object
// https://stackoverflow.com/questions/679915/how-do-i-test-for-an-empty-javascript-object
if (
child.count <= 0 &&
Object.keys(child.children).length &&
child.children.constructor === Object
) {
child.parent.children[child.key] = undefined
}
}
findAllWords(prefix) {
const output = []
// find the node with provided prefix
const node = this.findPrefix(prefix)
// No such prefix exists
if (node === null) return output
Trie.findAllWords(node, prefix, output)
return output
}
contains(word) {
// find the node with given prefix
const node = this.findPrefix(word)
// No such word exists
return node !== null && node.count !== 0
}
findOccurrences(word) {
// find the node with given prefix
const node = this.findPrefix(word)
// No such word exists
if (node === null) return 0
return node.count
}
}
export { Trie }