Skip to content

Instantly share code, notes, and snippets.

@blzjns
Last active April 11, 2022 07:24
Show Gist options
  • Save blzjns/902edf5208da72b99ade35ad1dd34d9b to your computer and use it in GitHub Desktop.
Save blzjns/902edf5208da72b99ade35ad1dd34d9b to your computer and use it in GitHub Desktop.
Find words using a tree-like struct (Trie)
/*
E.g.:
[root-node]
/ | \
B D S
/ | \
A O__ E__
/\ \ \ \
L T L R N__
| | | | \
L L M D S__E
*/
class Node {
constructor() {
this.keys = new Map();
this.end = false;
}
setEnd = () => this.end = true;
isEnd = () => this.end;
}
/* Trie Data Structure */
class Trie {
constructor() {
this.root = new Node();
}
add(input, node = this.root) {
if (input.length == 0) {
node.setEnd();
return;
}
else if (!node.keys.has(input[0])) {
node.keys.set(input[0], new Node());
}
return this.add(input.substr(1), node.keys.get(input[0]));
}
isWord(word) {
let node = this.root;
while (word.length > 1) {
if (!node.keys.has(word[0])) return false;
else {
node = node.keys.get(word[0]);
word = word.substr(1);
}
}
return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
}
print() {
const words = [];
function search(node, string) {
if (node.keys.size != 0) {
for (let letter of node.keys.keys()) search(node.keys.get(letter), string.concat(letter));
if (node.isEnd()) words.push(string);
}
else {
string.length > 0 ? words.push(string) : undefined;
return;
}
}
search(this.root, '');
return words.length > 0 ? words : mo;
}
}
myTrie = new Trie();
// add words
myTrie.add('ball');
myTrie.add('bat');
myTrie.add('doll');
myTrie.add('dork');
myTrie.add('do');
myTrie.add('dorm')
myTrie.add('send')
myTrie.add('sense')
console.log(myTrie.isWord('doll'))
console.log(myTrie.isWord('dor'))
console.log(myTrie.isWord('dorf'))
console.log(myTrie.print())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment