Skip to content

Instantly share code, notes, and snippets.

@rockarts
Created September 4, 2020 03:40
Show Gist options
  • Save rockarts/4274929dfbbb39102729ef4bb4491241 to your computer and use it in GitHub Desktop.
Save rockarts/4274929dfbbb39102729ef4bb4491241 to your computer and use it in GitHub Desktop.
Trie in Typescript
class TrieNode {
parent: TrieNode | null;
children: any = {}
key: string | null;
isTerminating = false
constructor(key: string | null, parent: TrieNode | null) {
this.key = key;
this.parent = parent
}
}
class Trie {
private root = new TrieNode(null, null)
insert(list: string[]) {
let current = this.root;
list.forEach((element) => {
if (current.children[element] == null) {
current.children[element] = new TrieNode(element, current)
}
current = current.children[element]
});
current.isTerminating = true
}
contains(list: string[]): Boolean {
let current = this.root;
list.forEach((element) => {
let child = current.children[element];
console.log(child.key);
if (child == null) {
return false;
}
current = child
});
return current.isTerminating
}
}
const trie = new Trie()
trie.insert("alex".split(""));
trie.insert("ali".split(""));
trie.insert("darcy".split(""));
trie.insert("estyn".split(""));
trie.insert("ian".split(""));
trie.insert("ivan".split(""));
trie.insert("josh".split(""));
trie.insert("mark".split(""));
trie.insert("michele".split(""));
trie.insert("robin".split(""));
trie.insert("sunny".split(""));
trie.insert("steven".split(""));
const alex = trie.contains("alex".split(""))
console.log(alex)
const steven = trie.contains("steven".split(""));
console.log(steven)
const ale = trie.contains("ale".split(""))
console.log(ale)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment