Skip to content

Instantly share code, notes, and snippets.

@fxfactorial
Created January 25, 2017 02:26
Show Gist options
  • Save fxfactorial/9db3527a6da24c8d354cb2180e262ea6 to your computer and use it in GitHub Desktop.
Save fxfactorial/9db3527a6da24c8d354cb2180e262ea6 to your computer and use it in GitHub Desktop.
Simple Trie implementation
var Trie = function () {
this.next = {};
this.is_word = false;
};
const code = c => c.codePointAt(0) - 'a'.codePointAt(0);
Trie.prototype.insert = function (key) {
let iter = this;
for (let c of key) {
if (iter.next[code(c)] === undefined) {
iter.next[code(c)] = new Trie;
}
iter = iter.next[code(c)];
}
iter.is_word = true;
};
Trie.prototype.search = function (key) {
let iter = this;
for (let c = 0; c < key.length; c++) {
const char_code = code(key[c]);
if (iter.next[char_code] === undefined) return false;
// Can't assume this because the string could keep going on
if (iter.next[char_code].is_word === true &&
c === key.length - 1)
return true;
iter = iter.next[char_code];
}
return false;
};
Trie.prototype.startsWith = function (prefix) {
let iter = this;
for (let c of prefix) {
const char_code = code(c);
if (iter.next[char_code] === undefined) return false;
iter = iter.next[char_code];
}
return true;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment