-
Notifications
You must be signed in to change notification settings - Fork 1
/
autocomplete.js
127 lines (106 loc) · 2.51 KB
/
autocomplete.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
var node = {
key : null
, value : null
, children : []
}
class Trie {
constructor() {
this.head = {
key : ''
, children: []
};
}
add(key){
var curNode = this.head
, newNode = null
, curChar = key.slice(0,1);
key = key.slice(1);
while(typeof curNode.children[curChar] !== "undefined"
&& curChar.length > 0){
curNode = curNode.children[curChar];
curChar = key.slice(0,1);
key = key.slice(1);
}
while(curChar.length > 0) {
newNode = {
key : curChar
, value : key.length === 0 ? null : undefined
, children : []
};
curNode.children[curChar] = newNode;
curNode = newNode;
curChar = key.slice(0,1);
key = key.slice(1);
}
};
search(key){
var curNode = this.head
, curChar = key.slice(0,1)
, d = 0;
key = key.slice(1);
var prev=curNode;
while(typeof curNode.children[curChar] !== "undefined" && curChar.length > 0){
res+=curChar;
curNode = curNode.children[curChar];
prev=curNode;
curChar = key.slice(0,1);
key = key.slice(1);
d += 1;
}
if (curNode.value === null && key.length === 0) {
return [d,null];
} else {
return [-1,prev];
}
}
remove(key){
var d = this.search(key);
if (d > -1){
removeH(this.head, key, d);
}
}
removeH(node, key, depth){
if (depth === 0 && Object.keys(node.children).length === 0){
return true;
}
var curChar = key.slice(0,1);
if (removeH(node.children[curChar], key.slice(1), depth-1)) {
delete node.children[curChar];
if (Object.keys(node.children).length === 0) {
return true;
} else {
return false;
}
} else {
return false;
}
}
}
var isLastNode=(root)=>{
for (let i = 0; i < 26; i++) {
var index = String.fromCharCode(97+i);
if (root.children[index]!==undefined)
return false;
}
return true;
}
var suggestionsRec=(root,currprefex)=>{
if(root===undefined||root===null||isLastNode(root)){
arrRes.push(currprefex);
return;
}
for(let i=0;i<26;i++){
var index = String.fromCharCode(97+i);
if(root.children[index]!==undefined){
currprefex+=index;
suggestionsRec(root.children[index],currprefex);
}
}
}
var trie=new Trie();
var res="";
var arrRes=[];
trie.add("ebraheem");
trie.add("ebraheam");
var [a,b]=trie.search("ebrah");
suggestionsRec(b,res)