-
-
Save rzhade3/e51d6d9c8154c15d5f6be287a46ad0bc to your computer and use it in GitHub Desktop.
Trie.js - super simple JavaScript implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Trie.js - super simple JS implementation | |
// https://en.wikipedia.org/wiki/Trie | |
// ----------------------------------------- | |
// we start with the TrieNode | |
class TrieNode { | |
constructor(key) { | |
// the "key" value will be the character in sequence | |
this.key = key; | |
// we keep a reference to parent | |
this.parent = null; | |
// we have hash of children | |
this.children = {}; | |
// check to see if the node is at the end | |
this.end = false; | |
} | |
// iterates through the parents to get the word. | |
// time complexity: O(k), k = word length | |
getWord() { | |
var output = []; | |
var node = this; | |
while (node !== null) { | |
output.unshift(node.key); | |
node = node.parent; | |
} | |
return output.join(''); | |
} | |
} | |
// ----------------------------------------- | |
// we implement Trie with just a simple root with null value. | |
class Trie { | |
constructor() { | |
this.root = new TrieNode(null); | |
this.length = 0; | |
} | |
// returns number of elements in trie. | |
length() { | |
return this.length; | |
} | |
// inserts a word into the trie. | |
// time complexity: O(k), k = word length | |
insert(word) { | |
var node = this.root; // we start at the root 😬 | |
this.length++; | |
// for every character in the word | |
for(var i = 0; i < word.length; i++) { | |
// check to see if character node exists in children. | |
if (!node.children[word[i]]) { | |
// if it doesn't exist, we then create it. | |
node.children[word[i]] = new TrieNode(word[i]); | |
// we also assign the parent to the child node. | |
node.children[word[i]].parent = node; | |
} | |
// proceed to the next depth in the trie. | |
node = node.children[word[i]]; | |
// finally, we check to see if it's the last word. | |
if (i == word.length-1) { | |
// if it is, we set the end flag to true. | |
node.end = true; | |
} | |
} | |
} | |
// check if it contains a whole word. | |
// time complexity: O(k), k = word length | |
contains(word) { | |
var node = this.root; | |
// for every character in the word | |
for(var i = 0; i < word.length; i++) { | |
// check to see if character node exists in children. | |
if (node.children[word[i]]) { | |
// if it exists, proceed to the next depth of the trie. | |
node = node.children[word[i]]; | |
} else { | |
// doesn't exist, return false since it's not a valid word. | |
return false; | |
} | |
} | |
// we finished going through all the words, but is it a whole word? | |
return node.end; | |
} | |
// returns every word with given prefix | |
// time complexity: O(p + n), p = prefix length, n = number of child paths | |
find(prefix) { | |
var node = this.root; | |
var output = []; | |
// for every character in the prefix | |
for(var i = 0; i < prefix.length; i++) { | |
// make sure prefix actually has words | |
if (node.children[prefix[i]]) { | |
node = node.children[prefix[i]]; | |
} else { | |
// there's none. just return it. | |
return output; | |
} | |
} | |
// recursively find all words in the node | |
_findAllWords(node, output); | |
return output; | |
}; | |
// recursive function to find all words in the given node. | |
_findAllWords(node, arr) { | |
// base case, if node is at a word, push to output | |
if (node.end) { | |
arr.unshift(node.getWord()); | |
} | |
// iterate through each children, call recursive findAllWords | |
for (var child in node.children) { | |
_findAllWords(node.children[child], arr); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment