Why Count Words with Given Prefix in DSA Typescript?

The Big Idea

What if you could find all words starting with a few letters instantly, no matter how big your list is?

The Scenario

Imagine you have a huge list of words, like a dictionary, and you want to find out how many words start with a certain set of letters, like "pre".

Doing this by checking each word one by one is like looking for all red apples in a giant basket by picking each apple up and checking its color.

The Problem

Checking every word manually takes a lot of time, especially if the list is very long.

It's easy to make mistakes or miss some words when doing this by hand or with simple loops.

This slow and error-prone method makes it hard to get quick answers.

The Solution

Using a special structure called a Trie, we can organize words so that all words with the same prefix share the same path.

This lets us quickly jump to the part where the prefix ends and count all words that start with it without checking each word individually.

Before vs After

✗ Before

let count = 0;
for (let word of words) {
  if (word.startsWith(prefix)) {
    count++;
  }
}

✓ After

class TrieNode {
  children = new Map<string, TrieNode>();
  count = 0;
}

// Insert words and count prefix matches efficiently

What It Enables

This lets us instantly find how many words start with any prefix, even in huge word lists, making searches fast and reliable.

Real Life Example

Search engines use this to suggest words or phrases as you type, by quickly counting how many words start with the letters you entered.

Key Takeaways

Manual checking is slow and error-prone for large word lists.

Tries organize words by prefixes to speed up counting.

Counting words with a prefix becomes fast and easy.