Autocomplete Feature using Trie Data Structure
Tags: algorithms
Published: 2023-03-17 14:45:24

## 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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hcbhci7pyoc083825ivt.png)
A trie takes up less space (characters) since repeat characters are stored in the same space.

## Autocomplete
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3mi0qkgsx8glplquwyni.png)
Autocomplete is like what you see on Google, where they help finish your sentence

## Technical Design (basic)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q8kbdynufq08lq4e24y2.png)
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](https://codesandbox.io/s/react-new)

and put this in the App.js file:
```javascript
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>
  );
}
```