Autocomplete Feature using Trie Data Structure

#algorithms

Why am I doing this?

Today's Leetcode Daily question was about Trie Data Structure. I remember most of the implementation even though I last did it a year ago. Somehow, I thought it would be nice to explore real-world implementations of data structures. Autocomplete seemed to be a really interesting feature, and it so happened to use Tries!

Trie Data Structure

A trie takes up less space (characters) since repeat characters are stored in the same space.

Autocomplete

Autocomplete is like what you see on Google, where they help finish your sentence

Technical Design (basic)

Somewhere, there should be some popularityWeightScore used to determine which results are given higher priority.

Performance: Brute Force VS Trie

Our basis of comparison will be a list of N words, with average length of S characters per word. Brute Force method would be comparing the text input string against each of the N words in the list.

	Brute Force	Trie
Space Complexity	O(N*S)	<O(N*S) (if have repeat characters)
Time Complexity	O(N*S)	O(S)

Code Snippet

Please run it on React Codesandbox

and put this in the App.js file:



import "./styles.css";
import React, { useState } from 'react';

// https://www.geeksforgeeks.org/auto-complete-feature-using-trie/
class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      if (!node.children[word[i]]) {
        node.children[word[i]] = new TrieNode();
      }
      node = node.children[word[i]];
    }
    node.isWord = true;
  }

  suggestHelper(root, list, curr) {
    if (root.isWord) {
      list.push(curr);
    }
    if (!Object.keys(root.children).length) {
      return;
    }
    for (let child in root.children) {
      this.suggestHelper(root.children[child], list, curr + child);
    }
  }

  suggest(prefix) {
    let node = this.root;
    let curr = "";
    for (let i = 0; i < prefix.length; i++) {
      if (!node.children[prefix[i]]) {
        return [];
      }
      node = node.children[prefix[i]];
      curr += prefix[i];
    }
    let list = [];
    this.suggestHelper(node, list, curr);
    return list;
  }
}

let words = ["hello", "dog", "hell", "cat", "a", "hel","help","helps","helping"];
let trie = new Trie();
words.forEach((word) => trie.insert(word));

export default function App() {
  const [inputText, setInputText] = useState("");
  const suggestions = trie.suggest(inputText)

  console.log(inputText)
  return (
    <div className="App">
      <h1>Hello CodeSandbox</h1>
      <input onChange={(e) => setInputText(e.target.value)}></input>
      {suggestions.map((text) => (<div>{text}</div>))}
    </div>
  );
}