Created
June 14, 2023 20:32
-
-
Save suyashgulati/9bc3f193f1b167037fc8967004fbe686 to your computer and use it in GitHub Desktop.
Dictionary implementation using Trie Tree
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
| // Classic Trie tree implementation for a dictionary that also supports wildcard search | |
| class TrieNode { | |
| constructor(isEndOfWord = false) { | |
| this.isEndOfWord = isEndOfWord; | |
| this.children = {}; | |
| } | |
| } | |
| class Dictionary { | |
| constructor(arr) { | |
| this.root = new TrieNode(); | |
| arr.forEach((w) => this.insert(w)); | |
| } | |
| insert(word) { | |
| let crawl = this.root; | |
| for (let j = 0; j < word.length; j++) { | |
| const ch = word.charAt(j); | |
| if (!crawl.children[ch]) { // if node does not exists for current character | |
| crawl.children[ch] = new TrieNode(j === word.length - 1); | |
| } | |
| crawl = crawl.children[ch]; // move to next node for the character | |
| } | |
| } | |
| isInDictRecur(word, node, index) { | |
| if (!node) return false; | |
| if (index === word.length && node.isEndOfWord) return true; | |
| const ch = word.charAt(index); | |
| if (ch === '*') { | |
| if (index === word.length - 1) return true; // when '*' is last | |
| return Object.keys(node.children).some((keyChar) => { | |
| return this.isInDictRecur(word, node.children[keyChar], index + 1); | |
| }); | |
| } else { | |
| return this.isInDictRecur(word, node.children[ch], index + 1); | |
| } | |
| } | |
| isInDict(word) { | |
| return this.isInDictRecur(word, this.root, 0); | |
| } | |
| } | |
| const wordArray = ['cat', 'car', 'boo', 'bar']; | |
| const dict = new Dictionary(wordArray); | |
| console.log(dict.isInDict('cat')); // true | |
| console.log(dict.isInDict('*a*')); // true | |
| console.log(dict.isInDict('cr*')); // false | |
| console.log(dict.isInDict('wat')); // false | |
| console.log(dict.isInDict('boo')); // true | |
| console.log(dict.isInDict('b*o')); // true |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment