Skip to content

Instantly share code, notes, and snippets.

@or9
Last active April 8, 2020 13:35
Show Gist options
  • Save or9/7e7605ec2772cc479be99017c1136240 to your computer and use it in GitHub Desktop.
Save or9/7e7605ec2772cc479be99017c1136240 to your computer and use it in GitHub Desktop.
Javascript Trie class
class TrieNode {
constructor (word) {
this.word = word;
this.nodes = {};
this.end = false;
}
}
export default class Trie {
constructor (word) {
this.root = new TrieNode("");
}
insert (word = "") {
var currentNode = this.root;
var letter = word.slice(0,1); // get first letter
word = word.slice(1); // get remainder of word
var childNode;
while (letter.length > 0) {
if (currentNode.nodes[letter] === undefined) {
childNode = new TrieNode(letter);
currentNode.nodes[letter] = childNode;
} else {
childNode = currentNode.nodes[letter];
}
currentNode = childNode;
letter = word.slice(0, 1);
word = word.slice(1);
}
childNode.end = true;
}
search (word = "") {
var currentNode = this.root;
var letter = word.slice(0, 1);
word = word.slice(1);
while (letter.length > 0) {
if (currentNode.nodes[letter]) {
currentNode = currentNode.nodes[letter];
if (word.length === 0) {
// if search is longer than nodes, ...
return currentNode.end;
}
letter = word.slice(0, 1);
word = word.slice(1);
} else {
return false;
}
}
}
startsWith (wordPrefix = "") {
var currentNode = this.root;
var letter = wordPrefix.slice(0, 1);
wordPrefix = wordPrefix.slice(1);
while (letter.length > 0) {
if (currentNode.nodes[letter]) {
currentNode = currentNode.nodes[letter];
letter = wordPrefix.slice(0, 1);
wordPrefix = wordPrefix.slice(1);
} else {
return false;
}
}
return true;
}
//TODO: #count (word)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment