GAZAR

Principal Engineer | Mentor

Trie Algorithm for Efficient Autocomplete

Trie Algorithm for Efficient Autocomplete

Trie, also known as a prefix tree, is a tree-like data structure used for efficient retrieval of strings with a common prefix. Each node in the Trie represents a single character of the alphabet. By traversing the Trie based on the characters of the input prefix, we can efficiently retrieve all words that match the given prefix.

Implementation in TypeScript:

Let's implement a Trie data structure along with autocomplete functionality in TypeScript:

class TrieNode {
  children: Map<string, TrieNode>;
  isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  root: TrieNode;

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

  insert(word: string): void {
    let node = this.root;
    for (let char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  search(prefix: string): string[] {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children.has(char)) {
        return []; // Prefix not found, return empty array
      }
      node = node.children.get(char)!;
    }
    return this.collectWords(node, prefix);
  }

  private collectWords(node: TrieNode, prefix: string): string[] {
    let words: string[] = [];
    if (node.isEndOfWord) {
      words.push(prefix);
    }
    for (let [char, childNode] of node.children) {
      words = words.concat(this.collectWords(childNode, prefix + char));
    }
    return words;
  }
}


// Example usage
const trie = new Trie();
trie.insert("apple");
trie.insert("application");
trie.insert("banana");

console.log(trie.search("app")); // Output: ['apple', 'application']

The Trie algorithm provides an efficient solution for implementing autocomplete functionality in TypeScript applications. By organizing words in a Trie data structure and traversing it based on the input prefix, we can quickly retrieve relevant suggestions in real-time. Incorporating Trie-based autocomplete can significantly enhance the usability and user experience of applications, making them more intuitive and user-friendly.

More: