Count Words with Given Prefix in DSA Java

Mental Model

We want to find how many words start with a certain beginning part (prefix). We look through each word and check if it starts with that prefix.

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

Words: [apple, app, ape, bat, ball]
Prefix: 'ap'
Goal: Count words starting with 'ap'

List:
[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null
Prefix: ↑ 'ap'

Dry Run Walkthrough

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

Goal: Count how many words start with the prefix "ap"

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

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: We need to check each word to see if it starts with the prefix

Step 2: 'apple' starts with 'ap', count = 1

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Increment count because 'apple' matches prefix

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

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Continue checking next word

Step 4: 'app' starts with 'ap', count = 2

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Increment count because 'app' matches prefix

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

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Continue checking next word

Step 6: 'ape' starts with 'ap', count = 3

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Increment count because 'ape' matches prefix

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

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Continue checking next word

Step 8: 'bat' does not start with 'ap', count remains 3

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Do not increment count because 'bat' does not match prefix

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

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Continue checking last word

Step 10: 'ball' does not start with 'ap', count remains 3

[apple] -> [app] -> [ape] -> [bat] -> [ball] -> null

Why: Do not increment count because 'ball' does not match prefix

Result:

Final count = 3
Words starting with 'ap': apple -> app -> ape -> null

Annotated Code

DSA Java

import java.util.*;

public class CountWordsWithPrefix {

    // Function to count words starting with given prefix
    public static int countPrefix(List<String> words, String prefix) {
        int count = 0;
        for (String word : words) {
            // Check if current word starts with prefix
            if (word.startsWith(prefix)) {
                count++; // Increment count if prefix matches
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List<String> words = Arrays.asList("apple", "app", "ape", "bat", "ball");
        String prefix = "ap";
        int result = countPrefix(words, prefix);
        System.out.println("Count of words starting with '" + prefix + "': " + result);
    }
}

for (String word : words) {

iterate over each word to check prefix

if (word.startsWith(prefix)) {

check if current word starts with the prefix

count++;

increment count when prefix matches

Output

Count of words starting with 'ap': 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 counter variable, no extra space grows with input size

vs Alternative: Compared to building a trie for prefix queries, this simple scan is easier but slower for many queries; trie offers faster repeated prefix counts but uses more memory

Edge Cases

empty list of words

count is zero because no words to check

DSA Java

for (String word : words) {

empty prefix string

all words count because every word starts with empty string

DSA Java

if (word.startsWith(prefix)) {

no words start with prefix

count remains zero

DSA Java

if (word.startsWith(prefix)) {

When to Use This Pattern

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

Common Mistakes

Mistake: Checking if prefix starts with word instead of word starts with prefix
Fix: Use word.startsWith(prefix) to correctly check prefix match

Mistake: Not handling empty prefix which matches all words
Fix: Allow empty prefix and count all words as matching

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.

Practice

1. What does the problem "Count Words with Given Prefix" ask you to do?

easy

A. Count how many words in a list start with a specific prefix

B. Find the longest word in a list

C. Count the total number of characters in all words

D. Sort the words alphabetically

Solution

1. Step 1: Understand the prefix concept

   The prefix is the starting part of a word. We need to check if words start with this prefix.

2. Step 2: Count matching words

   We count all words that begin with the given prefix from the list.

3. Final Answer:

   Count how many words in a list start with a specific prefix -> Option A

4. Quick Check:

   Prefix means start of word = Count matching words [OK]

Hint: Focus on words starting exactly with the prefix [OK]

Common Mistakes:

• Counting words containing prefix anywhere, not just start
• Confusing prefix with suffix
• Counting characters instead of words

2. Which of the following Java code snippets correctly checks if a string word starts with a prefix pref?

easy

A. word.endsWith(pref)

B. word.contains(pref)

C. word.equals(pref)

D. word.startsWith(pref)

Solution

1. Step 1: Recall Java String methods

   Java's startsWith method checks if a string begins with a given prefix.

2. Step 2: Match method to requirement

   Since we want to check the start, word.startsWith(pref) is correct.

3. Final Answer:

   word.startsWith(pref) -> Option D

4. Quick Check:

   startsWith checks prefix = word.startsWith(pref) [OK]

Hint: Use startsWith() to check prefix in Java strings [OK]

Common Mistakes:

• Using contains() which checks anywhere in string
• Using equals() which checks full string equality
• Using endsWith() which checks suffix

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

String[] words = {"apple", "app", "application", "banana"};
String prefix = "app";
int count = 0;
for (String w : words) {
    if (w.startsWith(prefix)) {
        count++;
    }
}
System.out.println(count);

medium

A. 3

B. 1

C. 2

D. 4

Solution

1. Step 1: Check each word against prefix "app"

   Words starting with "app" are "apple", "app", and "application" (3 words).

2. Step 2: Count matching words

   Count increments 3 times for these words.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 words start with "app" = 3 [OK]

Hint: Count words starting with prefix by checking each word [OK]

Common Mistakes:

• Counting only exact matches
• Counting words containing prefix anywhere
• Off-by-one errors in counting

4. The following code is intended to count words starting with a prefix but has a bug. What is the bug?

String[] words = {"cat", "car", "dog", "cart"};
String prefix = "car";
int count = 0;
for (int i = 0; i <= words.length; i++) {
    if (words[i].startsWith(prefix)) {
        count++;
    }
}
System.out.println(count);

medium

A. Prefix variable is not initialized

B. startsWith method is used incorrectly

C. Loop condition should be i < words.length, not i <= words.length

D. Array words is empty

Solution

1. Step 1: Analyze loop condition

   The loop runs from i = 0 to i <= words.length, which causes an IndexOutOfBoundsException because last index is words.length - 1.

2. Step 2: Correct loop condition

   Change condition to i < words.length to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be i < words.length, not i <= words.length -> Option C

4. Quick Check:

   Array index max is length-1 = fix loop condition [OK]

Hint: Use i < array.length to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring array index limits
• Misusing startsWith method

5. Given a list of words ["tree", "trie", "trigger", "trip", "trick"] and prefix "tri", which Java code snippet correctly counts the words starting with the prefix using streams?

hard

A. int count = Arrays.stream(words).map(w -> w.startsWith(prefix)).count();

B. long count = Arrays.stream(words).filter(w -> w.startsWith(prefix)).count();

C. long count = Arrays.stream(words).filter(w -> w.contains(prefix)).count();

D. int count = Arrays.stream(words).filter(w -> w.endsWith(prefix)).count();

Solution

1. Step 1: Use stream filter with startsWith

   The filter should keep words starting with the prefix using w.startsWith(prefix).

2. Step 2: Count filtered words

   Use count() to get the number of matching words. The result is a long type.

3. Final Answer:

   long count = Arrays.stream(words).filter(w -> w.startsWith(prefix)).count(); -> Option B

4. Quick Check:

   Filter with startsWith + count() = long count = Arrays.stream(words).filter(w -> w.startsWith(prefix)).count(); [OK]

Hint: Use stream filter with startsWith and count() for prefix count [OK]

Common Mistakes:

• Using map instead of filter
• Using contains instead of startsWith
• Using endsWith instead of startsWith