Why Prefix Search Using Trie in DSA Typescript?

The Big Idea

Discover how a simple tree can make searching words lightning fast!

The Scenario

Imagine you have a huge phone book and you want to find all contacts starting with "Sam". You flip pages one by one, checking each name carefully.

The Problem

This manual search is slow and tiring. You waste time checking every name, even those that don't start with "Sam". It's easy to miss some or get tired and make mistakes.

The Solution

A Trie is like a smart tree that organizes words by their letters. It lets you jump straight to all names starting with "Sam" without checking every entry. This saves time and effort.

Before vs After

✗ Before

function searchPrefix(words: string[], prefix: string): string[] {
  const result: string[] = [];
  for (const word of words) {
    if (word.startsWith(prefix)) result.push(word);
  }
  return result;
}

✓ After

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root = new TrieNode();
  // insert and prefix search methods here
}

What It Enables

It enables lightning-fast searches for all words sharing the same beginning letters, even in huge collections.

Real Life Example

When you type in a search bar on your phone, the suggestions appear instantly because the system uses a Trie to find words starting with what you typed.

Key Takeaways

Manual search checks every word, which is slow.

Trie organizes words by letters for quick prefix lookup.

Prefix search with Trie is fast and efficient for autocomplete.