## Introduction

As you know, Trie performs quite well on string operations such as searching and extracting a substring, especially when you have many substrings to search and simply performing normal search operations will It takes a lot of time and so in this article, I will show you a simple implementation of Trie data structure in JS language. 😃 You can use this implementation to understand how Trie works and use some of the available functions I provide. 😃 Note that this version is still quite simple and therefore may in some cases not be good for performance. 😅

## Implementation

The first thing you need is function(s) that lists the characters from a given string. I named these functions `forwardChars`

and `backwardChars`

respectively (they are generators). The Trie structure that I implement can allow you to search for a substring ending in a certain position, and that will be more convenient for you when performing tasks that involve replacing strings in `textarea`

elements of html. And the code should be straight forward as following:

```
function* forwardChars(str, index) {
index |= 0;
if (index < 0)
index = 0;
for (let i = index; i < str.length; i++)
yield str.charCodeAt(i);
}
function* backwardChars(str, index) {
if (index >= str.length || !Number.isSafeInteger(index)) {
index = str.length;
index--;
}
for (let i = index; i >= 0; i--)
yield str.charCodeAt(i);
}
```

In this version, I will use character codes instead of plain characters.

Next, I implemented the `TrieNode`

structure in Trie. The structure is pretty simple, it's an object that holds a `codes`

mapping that maps from the next character code to the next `TrieNode`

. In `TrieNode`

, I provide only one method which is `next`

to get the next node based on the given character code. `ensure`

parameter to ensure a new node will be created instead of `null`

being returned. And so, our source code will be

```
class TrieNode {
constructor() {
this.codes = new Map();
}
next(code, ensure) {
if (!this.codes.has(code)) {
let next = null;
if (ensure) {
next = new TrieNode();
this.codes.set(code, next);
}
return next;
}
return this.codes.get(code);
}
}
```

Next, we will have the `Trie`

class, which is the main class in the entire source code. In `Trie`

we will have

- The constructor which is used to create a root node which is a
`TrieNode`

. Here, we will have the`forward`

parameter to choose between forward or backward mode - The
`add(str)`

function will add a substring`str`

to`Trie`

- The
`match(str, index)`

function will match the substring`str`

at position`index`

and return the matched substring presented in`Trie`

And so our source code will be

```
class Trie {
constructor(forward = true) {
this.root = new TrieNode();
this.listChars = forward ? forwardChars : backwardChars;
}
add(str) {
let current = this.root;
for (let code of this.listChars(str))
current = current.next(code, true);
current.terminated = true;
}
match(str, index) {
let forward = this.listChars == forwardChars;
let current = this.root;
let count = 0;
let length = 0;
index |= 0;
for (let code of this.listChars(str, index)) {
count++;
current = current.next(code, false);
if (!current)
break;
if (current.terminated)
length = count;
}
return str.substr(forward ? index : ++index - length, length);
}
}
```

Combine them all and the full source code is

```
function* forwardChars(str, index) {
index |= 0;
if (index < 0)
index = 0;
for (let i = index; i < str.length; i++)
yield str.charCodeAt(i);
}
function* backwardChars(str, index) {
if (index >= str.length || !Number.isSafeInteger(index)) {
index = str.length;
index--;
}
for (let i = index; i >= 0; i--)
yield str.charCodeAt(i);
}
class TrieNode {
constructor() {
this.codes = new Map();
}
next(code, ensure) {
if (!this.codes.has(code)) {
let next = null;
if (ensure) {
next = new TrieNode();
this.codes.set(code, next);
}
return next;
}
return this.codes.get(code);
}
}
class Trie {
constructor(forward = true) {
this.root = new TrieNode();
this.listChars = forward ? forwardChars : backwardChars;
}
add(str) {
let current = this.root;
for (let code of this.listChars(str))
current = current.next(code, true);
current.terminated = true;
}
match(str, index) {
let forward = this.listChars == forwardChars;
let current = this.root;
let count = 0;
let length = 0;
index |= 0;
for (let code of this.listChars(str, index)) {
count++;
current = current.next(code, false);
if (!current)
break;
if (current.terminated)
length = count;
}
return str.substr(forward ? index : ++index - length, length);
}
}
```

## Using the class

The thing you should focus here is the `Trie`

class. Using the class is simple: initialize one, add substrings to it using `add`

method and the call `match`

on the string you want to extract at `index`

position. So the code

```
let ft = new Trie(); // this is forward trie
ft.add('abc');
ft.add('abcdef');
ft.add('xyz');
ft.match('abc', 0); // return 'abc'
ft.match('abc', 1); // return ''
ft.match('ab', 0); // return ''
ft.match('abcdef', 0); // return 'abcdef'
ft.match('abcdef', 1); // return ''
ft.match('xabcdef', 0); // return ''
ft.match('xabcdef', 1); // return 'abcdef'
ft.match('xyz', 0); // return 'xyz'
ft.match('xyz', 1); // return ''
ft.match('qxyz', 0); // return ''
let bt = new Trie(false); // this is backward trie
bt.add('abc');
bt.add('abcdef');
bt.add('xyz');
bt.match('abc', 2); // return 'abc'
bt.match('abc', 1); // return ''
bt.match('xabc', 3); // return 'abc'
bt.match('xyz', 2); // return 'xyz'
```

I hoped the implementation helped you see how to implement such a simple Trie in JS and hoped it can help you with search operations on strings. 😃 Have a nice day then. 😊

## Top comments (0)