Created
February 20, 2021 05:36
-
-
Save mikews93/cefd29440acbe6a2a16cdc0907b47231 to your computer and use it in GitHub Desktop.
Basic implementation of Trie data structure
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
| interface searchOptions { | |
| showHoleWord?: boolean; | |
| } | |
| class trieNode { | |
| public word: string; | |
| public children; | |
| public isWord: boolean; | |
| constructor(word: string) { | |
| this.word = word; | |
| this.children = {}; | |
| this.isWord = false; | |
| } | |
| } | |
| class Trie { | |
| private root: trieNode; | |
| constructor(words?: string[]) { | |
| this.root = new trieNode(''); | |
| this.addManyWords(words); | |
| } | |
| /** | |
| * @description inserts a words in the trie | |
| * @param word | |
| * @param previewsNode | |
| */ | |
| private insertWord (word:string, previewsNode = this.root): boolean { | |
| if (!word) { | |
| return previewsNode.isWord = true; | |
| } | |
| const splicedWord = word.split(''); | |
| const firstLetter = splicedWord.shift(); | |
| if (!previewsNode.children[firstLetter]) { | |
| previewsNode.children[firstLetter] = new trieNode(firstLetter) | |
| } | |
| this.insertWord(splicedWord.join(''), previewsNode.children[firstLetter]); | |
| } | |
| /** | |
| * @description Adds individual words to the trie | |
| * @param word | |
| */ | |
| public addWord(word: string): boolean { | |
| return this.insertWord(word); | |
| } | |
| /** | |
| * @description Adds several words in the trie at once | |
| * @param words string array of words | |
| */ | |
| public addManyWords(words: string[] = []): void { | |
| words.forEach((word) => this.insertWord(word)) | |
| } | |
| /** | |
| * @description returns the words that starts with the given prefix | |
| * @param prefix string from which the matches should start with | |
| * | |
| * @returns array of strings with matching words | |
| */ | |
| public searchPrefix(prefix: string, searchOptions: searchOptions = { showHoleWord: true }): string[] { | |
| if (!prefix.length|| !Object.keys(this.root.children).length) { | |
| return []; | |
| } | |
| let initNode: trieNode = this.root | |
| let prefixCopy = prefix; | |
| const matches: string[] = [] | |
| do { | |
| const splicedWord = prefixCopy.split(''); | |
| const firstLetter = splicedWord.shift(); | |
| prefixCopy = splicedWord.join(''); | |
| initNode = initNode.children[firstLetter]; | |
| if (prefixCopy.length == 0 && initNode) { | |
| this.assembleWords(initNode, searchOptions.showHoleWord ? prefix : '', matches); | |
| } | |
| } while (prefixCopy.length > 0 || initNode !== undefined) | |
| return matches; | |
| } | |
| /** | |
| * @description Iterates over the trie and reconstructs the words | |
| * @param partialTrie initial node to start iterating | |
| * @param assembleLetters reconstructed word | |
| * @param matches array of matches found | |
| */ | |
| private assembleWords(partialTrie: trieNode, assembleLetters: string, matches: string[]) { | |
| if (partialTrie.isWord){ | |
| matches.push(assembleLetters); | |
| } | |
| Object.keys(partialTrie.children).forEach((key) => { | |
| this.assembleWords(partialTrie.children[key], assembleLetters.concat(partialTrie.children[key].word), matches); | |
| }) | |
| } | |
| }; | |
| const parkList = ['Acadia', 'American Samoa', 'Arches', 'Badlands', 'Big Bend', 'Glacier', 'Glacier Bay', 'Glacier Baywatch', 'Grand Theft Auto', 'Halo', 'Cartagena', 'Medellin', 'Night City']; | |
| const myTrie = new Trie(parkList) | |
| console.log( {finds: myTrie.searchPrefix('Gla'), autoCompletes: myTrie.searchPrefix('A', { showHoleWord: false }) }); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment