Why Count Words with Given Prefix in DSA C++?

The Big Idea

What if you could find all words starting with your favorite letters instantly, no matter how big the list?

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 your friends in a crowd by calling their full names loudly and waiting for a response.

The Problem

Checking each word manually is very slow and tiring, especially if the list is very long.

You might miss some words or make mistakes counting them.

It's like trying to find all your friends in a stadium by shouting their names one by one--it takes too long and is easy to mess up.

The Solution

Using a smart structure like a prefix tree (Trie) helps you quickly find how many words start with the letters you want.

It organizes words by their letters, so you can jump straight to the part where words with your prefix live and count them fast.

Before vs After

✗ Before

int countWordsWithPrefix(vector<string> words, string prefix) {
    int count = 0;
    for (string word : words) {
        if (word.substr(0, prefix.size()) == prefix) {
            count++;
        }
    }
    return count;
}

✓ After

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    int prefixCount = 0;
};

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(string word) {
        TrieNode* current = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (!current->children[index]) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
            current->prefixCount++;
        }
    }
    int countWordsWithPrefix(string prefix) {
        TrieNode* current = root;
        for (char ch : prefix) {
            int index = ch - 'a';
            if (!current->children[index]) return 0;
            current = current->children[index];
        }
        return current->prefixCount;
    }
};

What It Enables

This lets you instantly know how many words start with any prefix, even in huge word lists, making searches lightning fast.

Real Life Example

Search engines use this to suggest words as you type, showing you popular words starting with the letters you entered.

Key Takeaways

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

Using a Trie organizes words by letters for fast prefix counting.

This method speeds up searches and suggestions in real applications.