Skip to content

Instantly share code, notes, and snippets.

@OrderAndCh4oS
Last active March 11, 2021 19:27
Show Gist options
  • Save OrderAndCh4oS/992662c85d9a5e7d9b4c0697f51b0426 to your computer and use it in GitHub Desktop.
Save OrderAndCh4oS/992662c85d9a5e7d9b4c0697f51b0426 to your computer and use it in GitHub Desktop.
Javascript Trie
class CharNode {
_char;
_phonetics = new Set();
_nextCharsLevel = {};
constructor(char) {
this._char = char;
}
get phoneticsLength() {
return this._phonetics.length;
}
get char() {
return this._char;
}
get phonetics() {
return this._phonetics;
}
get nextCharsLevel() {
return this._nextCharsLevel;
}
addPhonetic(phonetic) {
this._phonetics.add(phonetic);
}
}
class Trie {
_firstCharsLevel = {};
constructor() {}
addWord(word, phonetic) {
const charsArr = word.split('');
let currentCharLevel = this._firstCharsLevel;
let currentCharNode;
let currentChar = charsArr.shift();
while(charsArr.length) {
if(currentChar in currentCharLevel) {
currentCharNode = currentCharLevel[currentChar];
currentCharLevel = currentCharLevel[currentChar].nextCharsLevel;
currentChar = charsArr.shift();
continue;
}
currentCharLevel[currentChar] = new CharNode(currentChar);
currentCharNode = currentCharLevel[currentChar];
currentCharLevel = currentCharLevel[currentChar].nextCharsLevel;
currentChar = charsArr.shift();
}
currentCharNode.addPhonetic(phonetic);
}
findWord(word) {
const charsArr = word.split('');
let currentCharLevel = this._firstCharsLevel;
let currentChar;
let currentCharNode;
do {
currentChar = charsArr.shift();
if(!charsArr.length) return currentCharNode.phonetics;
if(!(currentChar in currentCharLevel)) return null;
currentCharNode = currentCharLevel[currentChar];
currentCharLevel = currentCharNode.nextCharsLevel;
} while(charsArr.length);
return null;
}
}
const trie = new Trie();
trie.addWord('à bout de', `/abudə/`);
trie.addWord('à bout portant', `/abupɔʁtɑ̃/`);
trie.addWord('à bras ouverts', `/abʁazuvɛʁ/`);
trie.addWord('a capella', `/akapela/`);
trie.addWord('à ce compte', `/asəkɔ̃t/`);
trie.addWord('à ce compte-là', `/asəkɔ̃tla/`);
trie.addWord('à ce moment-là', `/asəmɔmɑ̃la/`);
trie.addWord('à ce point', `/asəpwɛ̃/`);
console.log(trie.findWord('à bout de'));
console.log(trie.findWord('à bout portant'));
console.log(trie.findWord('a capella'));
console.log(trie.findWord('à ce compte'));
console.log(trie.findWord('à ce compte-là'));
console.log(trie.findWord('à ce moment-là'));
console.log(trie.findWord('à ce point'));
console.log(trie.findWord('hello'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment