Skip to content

Instantly share code, notes, and snippets.

@carefree-ladka
Last active August 21, 2024 09:24
Show Gist options
  • Select an option

  • Save carefree-ladka/be296ecee31c4ceab6e5d989d7944f9c to your computer and use it in GitHub Desktop.

Select an option

Save carefree-ladka/be296ecee31c4ceab6e5d989d7944f9c to your computer and use it in GitHub Desktop.
Trie implementation in JavaScript with Autocomplete feature
class TrieNode {
constructor() {
this.children = {}
this.eow = false
this.word = ""
}
}
class Trie {
constructor() {
this.root = new TrieNode()
}
insert = (word) => {
let node = this.root
for (const s of word) {
if (!node.children[s]) {
node.children[s] = new TrieNode(s)
}
node = node.children[s]
}
node.eow = true
node.word = word
}
search = (prefix) => {
let node = this.root
for (const s of prefix) {
if (!node.children[s]) return false
node = node.children[s]
}
return node.eow
}
autocomplete = (prefix) => {
let node = this.root
for (const s of prefix) {
if (!node.children[s]) return []
node = node.children[s]
}
return this.#getAllWordsIteratively(node)
}
#getAllWords = (node, words = []) => {
if (node.eow) return words.push(node.word)
for (const child in node.children) {
this.#getAllWords(node.children[child], words)
}
return words
}
#getAllWordsIteratively = (node) => {
const stack = [{ node, prefix: "" }];
const words = [];
while (stack.length > 0) {
const { node, prefix } = stack.pop();
if (node.eow) {
words.push(prefix + node.word);
}
for (const childKey in node.children) {
const childNode = node.children[childKey];
stack.push({ node: childNode, prefix: prefix + node.word });
}
}
return words;
}
}
const trie = new Trie()
trie.insert('pass')
trie.insert('past')
trie.insert('part')
console.log(trie.search('apple')); //false
console.log(trie.autocomplete('pas')); //[ 'past', 'pass' ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment