Count Words with Given Prefix in DSA Javascript

Mental Model

We want to find how many words start with a certain beginning part (prefix). We check each word to see if it begins with that prefix.

Analogy: Imagine you have a box of books and you want to count how many titles start with the word 'The'. You look at each title and count only those that start with 'The'.

Words: [apple, app, application, banana, bat]
Prefix: app
Check each word if it starts with 'app'

Dry Run Walkthrough

Input: words: ['apple', 'app', 'application', 'banana', 'bat'], prefix: 'app'

Goal: Count how many words start with 'app'

Step 1: Check if 'apple' starts with 'app'

apple (starts with 'app') -> count = 1

Why: We found one word starting with the prefix

Step 2: Check if 'app' starts with 'app'

apple -> app (starts with 'app') -> count = 2

Why: Another word matches the prefix

Step 3: Check if 'application' starts with 'app'

apple -> app -> application (starts with 'app') -> count = 3

Why: Another word matches the prefix

Step 4: Check if 'banana' starts with 'app'

apple -> app -> application -> banana (does not start with 'app') -> count = 3

Why: No match, count stays the same

Step 5: Check if 'bat' starts with 'app'

apple -> app -> application -> banana -> bat (does not start with 'app') -> count = 3

Why: No match, count stays the same

Result:

Final count = 3

Annotated Code

DSA Javascript

class PrefixCounter {
  constructor(words) {
    this.words = words;
  }

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

// Driver code
const words = ['apple', 'app', 'application', 'banana', 'bat'];
const prefix = 'app';
const counter = new PrefixCounter(words);
console.log(counter.countWordsWithPrefix(prefix));

for (const word of this.words) {

iterate over each word to check prefix

if (word.startsWith(prefix)) {

check if current word starts with the prefix

count++;

increment count for each matching word

Output

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(n) for storing the list of words

vs Alternative: Compared to building a trie for prefix counting, this approach is simpler but slower for many queries; trie offers faster prefix queries after setup

Edge Cases

empty words list

returns 0 because no words to check

DSA Javascript

for (const word of this.words) {

empty prefix string

counts all words because every word starts with empty string

DSA Javascript

if (word.startsWith(prefix)) {

no words match prefix

returns 0 because no word starts with given prefix

DSA Javascript

if (word.startsWith(prefix)) {

When to Use This Pattern

When you need to count how many strings start with a certain prefix, use this pattern of checking each word's start to find matches.

Common Mistakes

Mistake: Checking if prefix starts with word instead of word starts with prefix
Fix: Use word.startsWith(prefix) to correctly check the word's beginning

Mistake: Not handling empty prefix which should count all words
Fix: Allow empty prefix and count all words since all start with empty string

Summary

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

Use when you want to find how many words share the same beginning letters.

The key is to check each word's start against the prefix and count matches.