Created
November 2, 2017 16:31
-
-
Save levymoreira/b4e7afe1452e610f3c46bb06217ceaa1 to your computer and use it in GitHub Desktop.
Trie JS
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 Node { | |
constructor(char, isWordComplete = false) { | |
this.char = char; | |
this.isWordComplete = isWordComplete; | |
this.children = new Map(); // Map<char, Node> | |
} | |
} | |
class Trie { | |
constructor() { | |
this.head = new Node(''); | |
} | |
insert(word) { | |
let currentNode = this.head; | |
word.split("").forEach((char, i) => { | |
if (currentNode.children.get(char) !== undefined) { | |
currentNode = currentNode.children.get(char); | |
if (i === word.length - 1) | |
currentNode.isWordComplete = true; | |
} else { | |
const newNode = new Node(char, i === word.length - 1); | |
currentNode.children.set(char, newNode); | |
currentNode = newNode; | |
} | |
}); | |
} | |
search(word) { | |
let currentNode = this.head; | |
const chars = word.split(''); | |
for (let i = 0; i < chars.length; i ++) { | |
const char = chars[i]; | |
currentNode = currentNode.children.get(char); | |
if (!currentNode) | |
return false; | |
if (i === word.length - 1) | |
return currentNode.isWordComplete; | |
} | |
} | |
startsWith(prefix) { | |
let currentNode = this.head; | |
const chars = prefix.split(''); | |
for (let char of chars) { | |
currentNode = currentNode.children.get(char); | |
if (!currentNode) | |
return false; | |
} | |
return true; | |
} | |
} | |
const test = (currentResult, expectedResult) => { | |
if (currentResult !== expectedResult) { | |
console.log('Error!'); | |
} else { | |
console.log('Success.'); | |
} | |
} | |
var obj = new Trie(); | |
obj.insert('trie'); | |
obj.insert('levymoreira'); | |
obj.insert('levy'); | |
test(obj.search('trie'), true); | |
test(obj.search('t'), false); | |
test(obj.search('a'), false); | |
test(obj.search('levy'), true); | |
test(obj.startsWith('tr'), true); | |
test(obj.startsWith('a'), false); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment