Count Words with Given Prefix in DSA C# - 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

↓

Return count of words under this node

Traverse the prefix characters in the trie. If all prefix chars exist, return the count of words starting from the last prefix node.

Execution Sample

DSA C#

Insert words: "apple", "app", "ape", "bat"
Count words with prefix "ap"

Build a trie with words, then count how many words start with prefix "ap".

Execution Table

Step	Operation	Current Node	Prefix Char	Child Exists?	Action	Words Count at Node	Visual State
1	Start at root	root	a	Yes	Move to 'a' node	3	root -> a(3)
2	Check next char	a	p	Yes	Move to 'p' node	3	root -> a(3) -> p(3)
3	Prefix end reached	p	-	-	Return count 3	3	root -> a(3) -> p(3)
4	End	-	-	-	Done	-	Final count = 3

💡 Prefix fully matched at node 'p', count 3 words start with 'ap'

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
currentNode	root	node 'a'	node 'p'	node 'p'	node 'p'
prefixChar	n/a	'a'	'p'	end	end
wordsCount	n/a	3	3	3	3

Key Moments - 3 Insights

Why do we check if the child node exists for each prefix character?

Because if any prefix character is missing, no words start with that prefix. See execution_table rows 1 and 2 where child existence is checked.

Why do we return the count at the last prefix node?

Because that node tracks how many words have that prefix. In execution_table row 3, count 3 means 3 words start with 'ap'.

What if the prefix is not found in the trie?

We stop traversal early and return 0 since no words start with that prefix. This is shown in the 'No' branch in concept_flow.

Visual Quiz - 3 Questions

Look at the execution_table, what is the words count at node 'p' after step 2?

A 2

B 3

C 1

D 0

💡 Hint

Check the 'Words Count at Node' column in row 2 of execution_table.

At which step does the traversal reach the end of the prefix?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look for 'Prefix end reached' in the 'Operation' column of execution_table.

If the prefix was "bat", what would happen at step 1?

A Child node for 'b' does not exist, return 0

B Return count 3 immediately

C Child node for 'b' exists, move to 'b'

D Traversal stops at root

💡 Hint

Refer to concept_flow and execution_table step 1 logic for child node existence.

Concept Snapshot

Count Words with Given Prefix in Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If any char missing, return 0
- After last char, return count stored at node
- Count tracks how many words share that prefix

Full Transcript

To count words with a given prefix, we use a trie data structure. We start at the root node and check each character of the prefix one by one. If the child node for a character exists, we move to that node. If any character is missing, we return zero because no words start with that prefix. When we reach the last character of the prefix, we return the count stored at that node, which tells how many words start with that prefix. For example, with words 'apple', 'app', 'ape', and 'bat', counting words with prefix 'ap' returns 3 because 'apple', 'app', and 'ape' start with 'ap'.

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. Sort words alphabetically

D. Replace the prefix in all words with another string

Solution

1. Step 1: Understand the problem statement

   The problem asks to count words that begin with a given prefix, not to sort or replace words.

2. Step 2: Identify the key action

   Counting words starting with the prefix is the main task.

3. Final Answer:

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

4. Quick Check:

   Count words with prefix = Count how many words in a list start with a specific prefix [OK]

Hint: Focus on words starting with prefix, not other operations [OK]

Common Mistakes:

• Confusing counting with sorting
• Thinking the task is to replace prefixes
• Ignoring the prefix condition

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

easy

A. if (word == prefix) { /* do something */ }

B. if (word.Contains(prefix)) { /* do something */ }

C. if (word.EndsWith(prefix)) { /* do something */ }

D. if (word.StartsWith(prefix)) { /* do something */ }

Solution

1. Step 1: Recall string methods in C#

   The method StartsWith checks if a string begins with a given substring.

2. Step 2: Compare options

   Contains checks anywhere in the string, EndsWith checks the end, and == checks exact equality.

3. Final Answer:

   if (word.StartsWith(prefix)) { /* do something */ } -> Option D

4. Quick Check:

   Use StartsWith to check prefix [OK]

Hint: Use StartsWith method to check prefix in C# strings [OK]

Common Mistakes:

• Using Contains instead of StartsWith
• Checking equality instead of prefix
• Using EndsWith which checks suffix

3. What is the output of the following C# code?

string[] words = {"apple", "app", "application", "banana"};
string prefix = "app";
int count = 0;
foreach (var word in words) {
    if (word.StartsWith(prefix)) {
        count++;
    }
}
Console.WriteLine(count);

medium

A. 2

B. 1

C. 3

D. 4

Solution

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

   Words: "apple" (yes), "app" (yes), "application" (yes), "banana" (no).

2. Step 2: Count matches

   Three words start with "app", so count = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Words starting with "app" = 3 [OK]

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

Common Mistakes:

• Counting only exact matches
• Including words that contain prefix but don't start with it
• Off-by-one counting errors

4. The following code is intended to count words starting with a prefix but gives wrong output. What is the error?

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++;
    }
}
Console.WriteLine(count);

medium

A. The loop condition should be i < words.Length instead of <=.

B. The prefix variable is incorrect.

C. The StartsWith method is used wrongly.

D. The count variable should be initialized inside the loop.

Solution

1. Step 1: Analyze the for loop condition

   The loop runs from i = 0 to i <= words.Length, which causes an index out of range error because valid indices are 0 to words.Length - 1.

2. Step 2: Correct the loop condition

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

3. Final Answer:

   The loop condition should be i < words.Length instead of <=. -> Option A

4. Quick Check:

   Loop index must be less than array length [OK]

Hint: Use i < array.Length to avoid index errors in loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Reinitializing count inside loop
• Misusing StartsWith method

5. Given a list of words ["tree", "trie", "trigger", "trip", "try", "matrix"] and prefix "tri", which C# code snippet correctly counts the words starting with the prefix and prints the count?

hard

A. int count = 0; foreach(var word in words) { if(word.Contains(prefix)) count++; } Console.WriteLine(count);

B. int count = words.Count(word => word.StartsWith(prefix)); Console.WriteLine(count);

C. int count = 0; for(int i=0; i<=words.Length; i++) { if(words[i].StartsWith(prefix)) count++; } Console.WriteLine(count);

D. int count = words.Length; Console.WriteLine(count);

Solution

1. Step 1: Understand the requirement

   We need to count words starting exactly with prefix "tri".

2. Step 2: Evaluate each option

   int count = words.Count(word => word.StartsWith(prefix)); Console.WriteLine(count); uses LINQ Count with StartsWith correctly.
   int count = 0; foreach(var word in words) { if(word.Contains(prefix)) count++; } Console.WriteLine(count); uses Contains which counts words containing prefix anywhere.
   int count = 0; for(int i=0; i<=words.Length; i++) { if(words[i].StartsWith(prefix)) count++; } Console.WriteLine(count); has loop with <= causing index error.
   int count = words.Length; Console.WriteLine(count); counts all words ignoring prefix.

3. Final Answer:

   int count = words.Count(word => word.StartsWith(prefix)); Console.WriteLine(count); -> Option B

4. Quick Check:

   Use LINQ Count with StartsWith for prefix count [OK]

Hint: Use LINQ Count with StartsWith for concise prefix counting [OK]

Common Mistakes:

• Using Contains instead of StartsWith
• Loop index out of range errors
• Counting all words without prefix check