Count Words with Given Prefix in DSA Java - Execution Trace

Concept Flow - Count Words with Given Prefix

Start at root node

↓

For each character in prefix

↓

Check if child node exists

↓

Move to child

↓

After last char

↓

Count words in subtree

↓

Return count

Traverse the trie nodes for each prefix character; if path exists, count all words below the last node.

Execution Sample

DSA Java

class TrieNode {
  TrieNode[] children = new TrieNode[26];
  int count = 0;
}

int countWordsWithPrefix(TrieNode root, String prefix) {
  // traverse prefix
  // count words in subtree
}

This code traverses the trie for the prefix and counts words in the subtree.

Execution Table

Step	Operation	Current Node	Prefix Char	Pointer Changes	Visual State
1	Start at root	root	-	current = root	[root]
2	Check 'c'	root	c	current = root.children['c']	[root] -> [c]
3	Check 'a'	c	a	current = c.children['a']	[root] -> [c] -> [a]
4	Check 't'	a	t	current = a.children['t']	[root] -> [c] -> [a] -> [t]
5	Prefix found, count words	t	-	count words in subtree rooted at t	[root] -> [c] -> [a] -> [t*] (count=2)
6	Return count	t	-	-	Count = 2
7	End	-	-	-	Done

💡 Traversal ends after last prefix character; count words in subtree.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node 'c'	node 'a'	node 't'	node 't'	node 't'
count	0	0	0	0	2	2

Key Moments - 3 Insights

Why do we stop traversal if a child node for a prefix character is missing?

Because if the child node doesn't exist (see Step 2-4 in execution_table), the prefix is not in the trie, so no words match.

How do we count words after reaching the last prefix character node?

We count all words in the subtree rooted at that node (Step 5), summing counts of all descendant nodes.

Why do we keep track of 'current' node during traversal?

To move step-by-step through the trie nodes matching prefix characters (tracked in variable_tracker).

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'current' node after Step 3?

A node 'c'

B node 'a'

C node 't'

D root

💡 Hint

Check the 'Pointer Changes' and 'Current Node' columns at Step 3.

At which step does the traversal stop because the prefix is fully matched?

A Step 2

B Step 5

C Step 4

D Step 6

💡 Hint

Look for the last prefix character checked in the 'Prefix Char' column.

If the prefix was 'car' instead of 'cat', what would happen at Step 4?

A Traversal stops because 'r' child does not exist

B Count words immediately

C Traversal moves to node 'r'

D Return 0 without traversal

💡 Hint

Refer to the 'Check child node exists' logic in concept_flow and execution_table steps.

Concept Snapshot

Count Words with Given Prefix in Trie:
- Traverse trie nodes for each prefix character
- If child node missing, prefix not found
- After last prefix char, count all words in subtree
- Return total count
- Uses pointer 'current' to track traversal

Full Transcript

To count words with a given prefix in a trie, start at the root node. For each character in the prefix, move to the corresponding child node if it exists. If at any point the child node does not exist, the prefix is not found and the count is zero. After reaching the last character of the prefix, count all words in the subtree rooted at that node by summing counts of all descendant nodes. The traversal uses a pointer called 'current' to track the node being visited. This method efficiently counts all words starting with the prefix.

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