Last active
March 11, 2021 19:27
-
-
Save OrderAndCh4oS/992662c85d9a5e7d9b4c0697f51b0426 to your computer and use it in GitHub Desktop.
Javascript Trie
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
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