Typescript implementation of trie/digital tree/radix tree/prefix tree/suffix tree.
Trie (derived from retrieval) is a type of k-ary search tree used for storing and searching a specific string from a set. It is used to store a large amount of strings. The pattern matching can be done efficiently using tries.
- Using trie, the key can be searched in O(M) time, where M is the maximum string length. However, the penalty is the storage requirements.
- Tries take less space when they contain a large number of short strings, as nodes are shared between the keys.
- Autocompletion.
- The longest prefix.
- Spell-checking software.
export interface INode {
children: Map<string, INode>;
isEndOfWord: boolean;
}
export interface ITrie {
insert: (key: string) => void;
remove: (key: string) => void;
search: (key: string) => boolean;
isEmpty: (node?: INode) => boolean;
getLeavesCount: (node?: INode) => number;
getHeight: (node?: INode) => number;
printTrie: () => string;
log: () => string;
getWords: () => string[];
}
export const trie: (keys?: string[]) => ITrie;
export const suffixTree: (text: string) => ITrie;const _trie = trie(['orange', 'apple']);
console.log(_trie.search('orange')); // true or false
_trie.insert('potato');
_trie.remove('potato');
console.log(_trie.log());
console.log(_trie.getWords()); // ['orange', 'apple']
console.log(_trie.printTrie());
console.log(_trie.longestCommonPrefix());const st = suffixTree('banana');
console.log(st.search('apple')); // false
console.log(st.search('banana')); // true
console.log(st.search('anana')); // true
console.log(st.search('nana')); // true
console.log(st.search('ana')); // true
console.log(st.search('na')); // true
console.log(st.search('a')); // trueSuffix tree usage
- Pattern Searching
- Finding the longest repeated substring
- Finding the longest common substring
- Finding the longest palindrome in a string