Skip to content

Instantly share code, notes, and snippets.

@AnishLushte07
Created April 27, 2020 14:41
Show Gist options
  • Save AnishLushte07/6f7239aba91a12b0ec10e177a04cf8b4 to your computer and use it in GitHub Desktop.
Save AnishLushte07/6f7239aba91a12b0ec10e177a04cf8b4 to your computer and use it in GitHub Desktop.
Implementation of Trie data structure in javascript
function Node() {
this.keys = new Map();
this.end = null;
this.setEnd = function() {
this.end = true;
}
this.isEnd = function() {
return this.end;
}
}
function Trie() {
this.root = new Node();
this.add = function(word, node = this.root) {
if (word) {
if (!node.keys.has(word[0])) {
node.keys.set(word[0], new Node())
return this.add(word.substr(1), node.keys.get(word[0]));
} else {
return this.add(word.substr(1), node.keys.get(word[0]))
}
}
node.setEnd();
return;
}
this.isWord = function(word, node = this.root) {
while (word.length > 1) {
if (!node) return false;
if (node.keys.has(word[0])) {
node = node.keys.get(word[0]);
word = word.substr(1);
} else {
return false;
}
}
return !!(node.keys.has(word) && node.keys.get(word).end);
}
this.print = function() {
const words = [];
let search = function(node, str) {
for (let key of node.keys.keys()) {
if (!key) return;
let l = str.concat(key);
if (node.keys.get(key).end) {
words.push(l);
}
search(node.keys.get(key), l);
}
}
search(this.root, "");
return words;
}
}
const s = new Trie();
s.add('ball');
s.add('bat');
s.add('doll');
s.add('dork');
s.add('do');
s.add('dorm')
s.add('send')
s.add('sense')
console.log(s.isWord('dollaaa'))
console.log(s.isWord('dor'))
console.log(s.isWord('dorf'))
console.log(s.print())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment