Count Words with Given Prefix in DSA Typescript

Mental Model

We want to find how many words start with a certain beginning part. We look at each word and check if it begins with that part.

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 if it starts with 'The'.

words: [apple, app, ape, bat, ball]
prefix: app

Check each word:
apple -> starts with app
app -> starts with app
ape -> does not
bat -> does not
ball -> does not

Dry Run Walkthrough

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

Goal: Count how many words start with 'app'

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

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

Why: We found one word starting with the prefix

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

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

Why: Another word matches the prefix

Step 3: Check 'ape' if it starts with 'app'

apple, app, ape (does not start with 'app') -> count = 2

Why: This word does not match the prefix, so count stays

Step 4: Check 'bat' if it starts with 'app'

apple, app, ape, bat (does not start with 'app') -> count = 2

Why: No match, count unchanged

Step 5: Check 'ball' if it starts with 'app'

apple, app, ape, bat, ball (does not start with 'app') -> count = 2

Why: No match, count unchanged

Result:

Final count = 2

Annotated Code

DSA Typescript

class WordPrefixCounter {
  words: string[];

  constructor(words: string[]) {
    this.words = words;
  }

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

// Driver code
const words = ['apple', 'app', 'ape', 'bat', 'ball'];
const prefix = 'app';
const counter = new WordPrefixCounter(words);
console.log(counter.countWordsStartingWith(prefix));

for (const word of this.words) {

iterate over each word in the list

if (word.startsWith(prefix)) {

check if current word begins with the prefix

count++;

increment count when prefix matches

Output

2

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: A trie data structure can speed up prefix queries to O(m) after building, but building the trie costs O(n * m)

Edge Cases

empty words list

count returns 0 because no words to check

DSA Typescript

for (const word of this.words) {

empty prefix string

all words start with empty prefix, so count equals total words

DSA Typescript

if (word.startsWith(prefix)) {

no words start with prefix

count returns 0 as no matches found

DSA Typescript

if (word.startsWith(prefix)) {

When to Use This Pattern

When you need to count how many strings start with a certain beginning, use a simple loop with prefix check or a trie for faster repeated queries.

Common Mistakes

Mistake: Checking if prefix is inside the word anywhere instead of only at the start
Fix: Use word.startsWith(prefix) instead of word.includes(prefix)

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 exactly.

Practice

1. What does the function countWordsStartingWith(words: string[], prefix: string): number do in the context of counting words with a given prefix?

easy

A. Counts the total number of characters in all words

B. Counts how many words contain the prefix anywhere inside

C. Counts how many words in the list start with the given prefix

D. Returns the longest word starting with the prefix

Solution

1. Step 1: Understand the function purpose

   The function is designed to count words that begin with a specific prefix, not just contain it anywhere.

2. Step 2: Compare options with function goal

   Only Counts how many words in the list start with the given prefix matches the goal of counting words starting exactly with the prefix.

3. Final Answer:

   Counts how many words in the list start with the given prefix -> Option C

4. Quick Check:

   Counting words starting with prefix = Counts how many words in the list start with the given prefix [OK]

Hint: Look for words starting exactly with prefix, not containing it [OK]

Common Mistakes:

• Confusing 'start with' and 'contain' prefix
• Thinking it returns words instead of count
• Assuming it counts characters, not words

2. Which of the following TypeScript code snippets correctly counts words starting with a prefix pre in an array words?

easy

A. words.filter(word => word.startsWith(pre)).length

B. words.map(word => word.startsWith(pre)).length

C. words.reduce((count, word) => count + word.includes(pre), 0)

D. words.forEach(word => word.startsWith(pre))

Solution

1. Step 1: Identify correct method to filter words

   The filter method returns an array of words starting with the prefix, then length counts them.

2. Step 2: Check other options for correctness

   words.map(word => word.startsWith(pre)).length returns an array of booleans, so length is total words, not count of matches. words.reduce((count, word) => count + word.includes(pre), 0) uses includes incorrectly and sums booleans without conversion. words.forEach(word => word.startsWith(pre)) does not return a count.

3. Final Answer:

   words.filter(word => word.startsWith(pre)).length -> Option A

4. Quick Check:

   Filter + length counts matches = words.filter(word => word.startsWith(pre)).length [OK]

Hint: Use filter with startsWith, then get length [OK]

Common Mistakes:

• Using map instead of filter for counting
• Using includes instead of startsWith
• Using forEach without counting

3. What is the output of the following TypeScript code?

const words = ['apple', 'app', 'application', 'banana', 'apply'];
const prefix = 'app';
const count = words.filter(word => word.startsWith(prefix)).length;
console.log(count);

medium

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Identify words starting with 'app'

   Words starting with 'app' are 'apple', 'app', 'application', and 'apply' (4 words).

2. Step 2: Count these words

   Counting them gives 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Words starting with 'app' = 4 [OK]

Hint: Count words starting exactly with prefix 'app' [OK]

Common Mistakes:

• Counting 'banana' mistakenly
• Counting only exact 'app' word
• Confusing includes with startsWith

4. The following TypeScript code is intended to count words starting with prefix pre, but it returns 0. What is the error?

const words = ['prefix', 'preach', 'prevent', 'post'];
const pre = 'pre';
let count = 0;
for (let i = 0; i < words.length; i++) {
  if (words[i].startWith(pre)) {
    count++;
  }
}
console.log(count);

medium

A. Method name should be startsWith, not startWith

B. Variable pre is not defined

C. Loop should start from 1, not 0

D. count should be initialized to 1

Solution

1. Step 1: Check method name correctness

   The method to check prefix is startsWith, but code uses startWith, which is undefined.

2. Step 2: Understand effect of typo

   Because of the typo, condition is always false, so count remains 0.

3. Final Answer:

   Method name should be startsWith, not startWith -> Option A

4. Quick Check:

   Correct method name fixes count [OK]

Hint: Check method spelling: startsWith, not startWith [OK]

Common Mistakes:

• Using startWith instead of startsWith
• Incorrect loop index start
• Wrong count initialization

5. Given a large list of words, which data structure would optimize counting how many words start with a given prefix efficiently for multiple queries?

hard

A. Array sorted alphabetically

B. Stack storing words

C. Hash Map with full words as keys

D. Trie (Prefix Tree)

Solution

1. Step 1: Understand prefix query optimization

   Trie stores words by characters in a tree, allowing fast prefix searches.

2. Step 2: Compare other data structures

   Sorted arrays require binary search but less efficient for many prefix queries. Hash maps store full words, not prefixes. Stacks do not support prefix queries efficiently.

3. Final Answer:

   Trie (Prefix Tree) -> Option D

4. Quick Check:

   Trie enables fast prefix counts [OK]

Hint: Use Trie for fast prefix counting in many queries [OK]

Common Mistakes:

• Choosing array or hash map for prefix queries
• Not knowing Trie supports prefix efficiently
• Confusing stack usage for prefix search