forked from TheAlgorithms/JavaScript
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrie.js
More file actions
Latest commit
121 lines (108 loc) · 3.27 KB
/
Copy pathTrie.js
File metadata and controls
121 lines (108 loc) · 3.27 KB
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
constTrieNode=functionTrieNode(key,parent){
this.key=key
this.count=0
this.children=Object.create(null)
if(parent===undefined){
this.parent=null
}else{
this.parent=parent
}
}
functionTrie(){
// create only root with null key and parent
this.root=newTrieNode(null,null)
}
// Recursively finds the occurrence of all words in a given node
Trie.findAllWords=function(root,word,output){
if(root===null)return
if(root.count>0){
if(typeofoutput==='object'){output.push({ word,count: root.count})}
}
letkey
for(keyinroot.children){
word+=key
this.findAllWords(root.children[key],word,output)
word=word.slice(0,-1)
}
}
Trie.prototype.insert=function(word){
if(typeofword!=='string')return
if(word===''){
this.root.count+=1
return
}
letnode=this.root
constlen=word.length
leti
for(i=0;i<len;i++){
if(node.children[word.charAt(i)]===undefined){node.children[word.charAt(i)]=newTrieNode(word.charAt(i),node)}
node=node.children[word.charAt(i)]
}
node.count+=1
}
Trie.prototype.findPrefix=function(word){
if(typeofword!=='string')returnnull
letnode=this.root
constlen=word.length
leti
// After end of this loop node will be at desired prefix
for(i=0;i<len;i++){
if(node.children[word.charAt(i)]===undefined)returnnull// No such prefix exists
node=node.children[word.charAt(i)]
}
returnnode
}
Trie.prototype.remove=function(word,count){
if(typeofword!=='string')return
if(typeofcount!=='number')count=1
elseif(count<=0)return
// for empty string just delete count of root
if(word===''){
if(this.root.count>=count)this.root.count-=count
elsethis.root.count=0
return
}
letchild=this.root
constlen=word.length
leti,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
elsechild.count=0
// If some occurrences are left we dont delete it or else
// if the object forms some other objects prefix we dont 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
}
}
Trie.prototype.findAllWords=function(prefix){
constoutput=[]
// find the node with provided prefix
constnode=this.findPrefix(prefix)
// No such prefix exists
if(node===null)returnoutput
Trie.findAllWords(node,prefix,output)
returnoutput
}
Trie.prototype.contains=function(word){
// find the node with given prefix
constnode=this.findPrefix(word)
// No such word exists
if(node===null||node.count===0)returnfalse
returntrue
}
Trie.prototype.findOccurences=function(word){
// find the node with given prefix
constnode=this.findPrefix(word)
// No such word exists
if(node===null)return0
returnnode.count
}
export{Trie}