-
Notifications
You must be signed in to change notification settings - Fork 0
/
trie-search-tree.ts
129 lines (108 loc) · 3.43 KB
/
trie-search-tree.ts
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
class Node {
keys: { [key: string]: Node } = {};
end = false;
}
/**
* A trie search tree that stores words in an ordered tree structure in which
* each node represents an individual letter.
*/
export class Trie {
root = new Node();
/** Adds a new word to the trie. */
add(word: string): void {
if (!word.match(/^[A-Za-z]+$/)) {
throw new TypeError(
"Argument must be a single word with no special characters."
);
}
(function addFrom(node: Node, remainingLtrs: string): void {
if (remainingLtrs) {
if (node.keys[remainingLtrs[0]] === undefined) {
// Create new node at letter
node.keys[remainingLtrs[0]] = new Node();
}
// Move to next letter
addFrom(node.keys[remainingLtrs[0]], remainingLtrs.slice(1));
} else {
// Mark end of word
node.end = true;
}
})(this.root, word);
}
/** Checks if a specific word is currently stored in the trie. */
contains(string: string): boolean {
if (!string.match(/^[A-Za-z]+$/)) return false;
return (function searchFrom(node: Node, remainingLtrs: string): boolean {
if (remainingLtrs) {
if (node.keys[remainingLtrs[0]]) {
// Move to next letter
return searchFrom(
node.keys[remainingLtrs[0]],
remainingLtrs.slice(1)
);
} else {
// String not present
return false;
}
} else {
// Word exists if this node is an end point
return node.end;
}
})(this.root, string);
}
/**
* Removes a word from the trie, returning a boolean confirming whether or not
* the word was present (and was therefore removed).
*/
remove(word: string): boolean {
if (!word.match(/^[A-Za-z]+$/)) return false;
// Array of [current node, next letter] tuples
let wordNodes: Array<[Node, string]> = [];
const collectNodesFrom = (node: Node, remainingLtrs: string): boolean => {
wordNodes.push([node, remainingLtrs[0]]);
if (remainingLtrs) {
if (node.keys[remainingLtrs[0]]) {
// Move to next letter
return collectNodesFrom(
node.keys[remainingLtrs[0]],
remainingLtrs.slice(1)
);
} else {
// String not present
return false;
}
} else {
// Word exists if this node is an end point
return node.end;
}
};
if (!collectNodesFrom(this.root, word)) return false;
// Remove endpoint from last node
let [currentNode, nextLtr]: [Node, string] = wordNodes.pop();
currentNode.end = false;
let onSharedPath = Object.keys(currentNode.keys).length > 0;
// Remove nodes that aren't part of any other word
while (wordNodes.length && !onSharedPath) {
[currentNode, nextLtr] = wordNodes.pop();
delete currentNode.keys[nextLtr];
onSharedPath =
Object.keys(currentNode.keys).length > 0 || currentNode.end;
}
return true;
}
/** Clears the contents of the trie. */
clear(): void {
this.root = new Node();
}
/** Returns an array of all words stored in the trie. */
getAll(): string[] {
let words: string[] = [];
(function searchFrom(node: Node, wordSoFar: string): void {
if (node.end) words.push(wordSoFar);
for (const key of Object.keys(node.keys)) {
searchFrom(node.keys[key], wordSoFar + key);
}
})(this.root, "");
return words;
}
}