Count Words with Given Prefix in DSA C++

Mental Model

We want to find how many words start with a certain beginning part. We look through all words and count those that begin with that prefix.

Analogy: Imagine a library where you want to find how many books start with the letter 'A'. You scan the titles and count each one starting with 'A'.

Words: [apple, ape, april, bat, ball]
Prefix: ap
Count: ?

Dry Run Walkthrough

Input: words: [apple, ape, april, bat, ball], prefix: 'ap'

Goal: Count how many words start with 'ap'

Step 1: Check word 'apple' if it starts with 'ap'

apple -> starts with 'ap' -> count = 1

Why: We found one word starting with the prefix

Step 2: Check word 'ape' if it starts with 'ap'

apple, ape -> both start with 'ap' -> count = 2

Why: Another word matches the prefix

Step 3: Check word 'april' if it starts with 'ap'

apple, ape, april -> all start with 'ap' -> count = 3

Why: Third word matches prefix

Step 4: Check word 'bat' if it starts with 'ap'

apple, ape, april, bat -> bat does not start with 'ap' -> count = 3

Why: No increase because 'bat' does not match

Step 5: Check word 'ball' if it starts with 'ap'

apple, ape, april, bat, ball -> ball does not start with 'ap' -> count = 3

Why: No increase because 'ball' does not match

Result:

Count = 3

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Function to count words starting with given prefix
int countWordsWithPrefix(const vector<string>& words, const string& prefix) {
    int count = 0;
    for (const string& word : words) {
        // Check if word length is at least prefix length
        if (word.size() >= prefix.size()) {
            // Compare prefix part of word with prefix
            if (word.compare(0, prefix.size(), prefix) == 0) {
                count++; // Increment count if prefix matches
            }
        }
    }
    return count;
}

int main() {
    vector<string> words = {"apple", "ape", "april", "bat", "ball"};
    string prefix = "ap";
    int result = countWordsWithPrefix(words, prefix);
    cout << "Count = " << result << endl;
    return 0;
}

for (const string& word : words) {

iterate over each word to check prefix

if (word.size() >= prefix.size()) {

skip words shorter than prefix to avoid errors

if (word.compare(0, prefix.size(), prefix) == 0) {

check if word starts with prefix

count++;

increment count for matching prefix

Output

Count = 3

Complexity Analysis

Time: O(n * m) because we check each of the n words and compare up to m characters of the prefix

Space: O(1) because we only use a few variables for counting and comparisons

vs Alternative: A naive approach is similar here; using a trie could improve prefix queries but adds complexity and space

Edge Cases

empty words list

count remains zero because no words to check

DSA C++

for (const string& word : words) {

prefix longer than some words

those shorter words are skipped safely by size check

DSA C++

if (word.size() >= prefix.size()) {

no words match prefix

count remains zero after checking all words

DSA C++

if (word.compare(0, prefix.size(), prefix) == 0) {

When to Use This Pattern

When you need to count or find words starting with a certain beginning, look for prefix matching patterns because they simplify filtering words.

Common Mistakes

Mistake: Not checking if word length is at least prefix length before comparing
Fix: Add a length check to avoid out-of-range errors

Mistake: Using substring extraction instead of compare, which is less efficient
Fix: Use string.compare to check prefix without extra substring creation

Summary

Counts how many words in a list start with a given prefix.

Use when you want to filter or count words by their starting letters.

Check word length first, then compare prefix directly for efficient matching.