Trie vs Hash Map for Prefix Matching in DSA Typescript - Why the Distinction Matters

The Big Idea

What if you could find all words starting with 'Sam' instantly, no matter how big your list is?

The Scenario

Imagine you have a huge phone book and want to find all contacts starting with 'Sam'. You try to look through every name one by one to find matches.

The Problem

Going through every name manually is slow and tiring. It's easy to miss some matches or take too long, especially if the list is very big.

The Solution

A Trie organizes words by their letters, so you can quickly jump to all names starting with 'Sam' without checking every single name. It's like having a smart index that guides you straight to the matches.

Before vs After

✗ Before

const contacts = ['Sam', 'Samantha', 'Samuel', 'Sara'];
const results = contacts.filter(name => name.startsWith('Sam'));
console.log(results);

✓ After

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

class Trie {
  root = new TrieNode();
  insert(word: string) { /* insert logic */ }
  startsWith(prefix: string): string[] { /* prefix search logic */ }
}

const trie = new Trie();
['Sam', 'Samantha', 'Samuel', 'Sara'].forEach(name => trie.insert(name));
console.log(trie.startsWith('Sam'));

What It Enables

It enables lightning-fast prefix searches even in huge lists, making autocomplete and search features smooth and instant.

Real Life Example

When you type in a search box on your phone, the app quickly suggests words starting with what you typed, thanks to Tries organizing the dictionary behind the scenes.

Key Takeaways

Manual search checks every item, which is slow for big data.

Trie structures group words by letters for fast prefix lookup.

Using Tries makes autocomplete and prefix matching efficient and scalable.