Pierre Hedkvist

← Back to home

Autocomplete using Trie datastructure with Typescript

Ever wondered how the autocomplete feature work when you write some text into an input field, and suggestions appear matching your input. This can be implemented using a Trie. Its a search tree, containing keys that maps charcters to nodes. To find autocomplete suggestions, the tree is traversed depth-first.

Trie datastructure

In the above example you can find the following words: A, to, tea, ted, ten, i, in and inn.

Lets see how this can be implemented. This solution is based of the leetcode challenge 208. Implement Trie (Prefix Tree) 

class Node {
  children: Record<string, Node>;
  val: string;
  char: string;

  constructor(val = '', char = '') {
    this.val = val;
    this.children = {};
    this.char = char;
  }
}

The above Node class, will contain the character that is assoicated with each node. The children are the letters that follow each word. The final node associated with a word will contain the full string of that word.

Lets look at how we can construct this tree, given a list of words.

class Trie {
  root: Node;

  constructor() {
    this.root = new Node('', '');
  }
}

The Trie class is instantiated with an empty root node. From the root, we can look at the children and see a list of all of the first characters of all words present in the Trie.

insert(word: string): void {
        let curNode = this.root;
        word.split("").forEach((w, i) => {
            const isFinalChar = i === word.length - 1;
            const hasNode = curNode.children[w];
            if (hasNode) {
                curNode = hasNode;
            } else {
                // add a new node to curNode children.
                const newNode = new Node("", w);
                curNode.children[w] = newNode;
                curNode = newNode;
            }
            if (isFinalChar) {
                curNode.val = word;
            }
        });
    }

To insert elements to our trie, we map over each character, and see if a node already exists for that character and that level in the trie. On the final character, we mark that node with the full value of the string, this way we know we have reached the end of a full word.

search(word: string): boolean {
        let curNode = this.root;
        const array = word.split("");
        let i = 0;
        while (i < array.length) {
            const w = array[i];
            curNode = curNode.children[w];
            if (curNode === undefined) {
                return false;
            }
            i++;
        };
        return curNode ? curNode.val === word : false;
    }

To search for an element in the trie, we map over each character in the word, and try to see if we can go down the graph and check in the end if the final node value equals our word.

startsWith(prefix: string): boolean {
        let curNode = this.root;
        const array = prefix.split("");
        let i = 0;
        while (i < array.length) {
            const w = array[i];
            curNode = curNode.children[w]
            if (curNode === undefined) {
                return false;
            }
            i++;
        };
        return curNode ? (curNode.val === prefix || Object.keys(curNode.children).length > 0) : false;
    }

To check if we can find any values starting with certain character, we once again map over each character, and go down the graph, and finaly check if the final node has children or itself equals the value of the prefix.

Thats it. Full solution can be seen below.

class Node {
  children: Record<string, Node>;
  val: string;
  char: string;

  constructor(val = '', char = '') {
    this.val = val;
    this.children = {};
    this.char = char;
  }
}

class Trie {
  root: Node;

  constructor() {
    this.root = new Node('', '');
  }

  insert(word: string): void {
    let curNode = this.root;
    word.split('').forEach((w, i) => {
      const isFinalChar = i === word.length - 1;
      const hasNode = curNode.children[w];
      if (hasNode) {
        curNode = hasNode;
      } else {
        // add a new node to curNode children.
        const newNode = new Node('', w);
        curNode.children[w] = newNode;
        curNode = newNode;
      }
      if (isFinalChar) {
        curNode.val = word;
      }
    });
  }

  search(word: string): boolean {
    let curNode = this.root;
    const array = word.split('');
    let i = 0;
    while (i < array.length) {
      const w = array[i];
      curNode = curNode.children[w];
      if (curNode === undefined) {
        return false;
      }
      i++;
    }
    return curNode ? curNode.val === word : false;
  }

  startsWith(prefix: string): boolean {
    let curNode = this.root;
    const array = prefix.split('');
    let i = 0;
    while (i < array.length) {
      const w = array[i];
      curNode = curNode.children[w];
      if (curNode === undefined) {
        return false;
      }
      i++;
    }
    return curNode
      ? curNode.val === prefix || Object.keys(curNode.children).length > 0
      : false;
  }
}
← Back to home