Count Words with Given Prefix in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the problem 'Count Words with Given Prefix' ask you to do?

It asks you to find how many words in a list start with a specific prefix.

intermediate

Which data structure can efficiently help count words with a given prefix?

A Trie (prefix tree) can efficiently store words and count how many start with a given prefix.

beginner

How do you check if a word starts with a prefix in Java without a Trie?

You can use the String method startsWith(prefix) to check if a word begins with the prefix.

intermediate

What is the time complexity of counting words with a given prefix using a simple loop and startsWith?

It is O(n * m), where n is the number of words and m is the length of the prefix.

advanced

Why might a Trie be better than a simple loop for counting prefix matches?

A Trie can reduce repeated prefix checks by sharing common prefix paths, making prefix counting faster especially with many queries.

What does the method startsWith do in Java?

A Checks if a string ends with a given suffix

B Checks if a string begins with a given prefix

C Counts the number of words in a string

D Reverses the string

The startsWith method returns true if the string begins with the specified prefix.

Which data structure is best suited for prefix-based word counting?

A Trie

B Stack

C Array

D Queue

A Trie stores words by their prefixes, making prefix queries efficient.

If you have 1000 words and a prefix of length 3, what is the worst-case time complexity to count prefix matches using startsWith?

A O(3000)

B O(1000)

C O(3)

D O(1)

Each of the 1000 words is checked for the 3-character prefix, so O(1000 * 3) = O(3000).

What is a prefix in the context of strings?

A A substring at the end of a string

B A reversed string

C A substring at the beginning of a string

D Any substring inside a string

A prefix is a substring that starts at the beginning of a string.

Which of these is NOT a benefit of using a Trie for prefix counting?

A Faster prefix queries

B Avoids repeated prefix checks

C Memory efficiency for many words with shared prefixes

D Simpler code than using loops

Trie code is usually more complex than simple loops, but it is more efficient for prefix queries.

Explain how you would count words starting with a given prefix using a simple loop in Java.

Think about checking each word one by one.

Describe how a Trie data structure helps in counting words with a given prefix.

Imagine a tree where each branch is a letter.

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