Count Words with Given Prefix in DSA C++ - Execution Trace

Concept Flow - Count Words with Given Prefix

Start at root node

↓

For each char in prefix

↓

Check if char child exists?

No→Prefix not found, return 0

Yes↓

Move to child node

↓

Repeat for next char

↓

After last char

↓

Return count of words with this prefix

Start from the root of the trie and follow each character of the prefix. If any character is missing, return 0. Otherwise, after the last character, return the count of words that share this prefix.

Execution Sample

DSA C++

class TrieNode {
public:
  TrieNode* children[26];
  int prefixCount;
  TrieNode() : prefixCount(0) {
    for (int i = 0; i < 26; i++) children[i] = nullptr;
  }
};

int countWordsWithPrefix(TrieNode* root, const string& prefix) {
  TrieNode* curr = root;
  for (char c : prefix) {
    int idx = c - 'a';
    if (!curr->children[idx]) return 0;
    curr = curr->children[idx];
  }
  return curr->prefixCount;
}

This code counts how many words in the trie start with the given prefix by traversing nodes for each prefix character and returning the stored prefix count.

Execution Table

Step	Operation	Current Node	Character	Child Exists?	Action	Prefix Count	Visual State
1	Start at root	root	-	N/A	Move to next char	5	root(5)
2	Check 'a'	root	a	Yes	Move to child 'a'	3	root(5) -> a(3)
3	Check 'p'	a	p	Yes	Move to child 'p'	3	root(5) -> a(3) -> p(3)
4	Check 'p'	p	p	Yes	Move to child 'p'	2	root(5) -> a(3) -> p(3) -> p(2)
5	Check 'l'	p	l	Yes	Move to child 'l'	2	root(5) -> a(3) -> p(3) -> p(2) -> l(2)
6	Check 'e'	l	e	Yes	Move to child 'e'	1	root(5) -> a(3) -> p(3) -> p(2) -> l(2) -> e(1)
7	Prefix end	e	-	N/A	Return prefixCount	1	root(5) -> a(3) -> p(3) -> p(2) -> l(2) -> e(1)

💡 Traversal ends after last prefix character 'e'; prefixCount 1 returned.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
curr	root	node 'a'	node 'p'	node 'p'	node 'l'	node 'e'	node 'e'
prefixCount	-	3	3	2	2	1	1

Key Moments - 3 Insights

Why do we return 0 if a child node for a prefix character does not exist?

Because if any character in the prefix is missing in the trie, it means no word starts with that prefix, so the count is zero.

Why do we return prefixCount at the last node of the prefix?

The prefixCount at the last node stores how many words have that prefix (see Step 7 in execution_table), so returning it gives the total count of words starting with the prefix.

What does prefixCount represent at each node?

prefixCount counts how many words pass through that node, meaning how many words have the prefix up to that character (visible in variable_tracker and execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the current node and character checked?

A Node 'p', character 'p'

B Node 'a', character 'p'

C Node 'p', character 'l'

D Node 'root', character 'a'

💡 Hint

Check the 'Current Node' and 'Character' columns in execution_table row for Step 4.

At which step does the traversal reach the last character of the prefix?

A Step 5

B Step 7

C Step 6

D Step 4

💡 Hint

Look for the step where the last prefix character 'e' is checked in execution_table.

If the prefix was 'appx' instead of 'apple', what would happen in the execution_table?

A Traversal would return prefixCount at node 'p'

B Traversal would return 0 at the missing child for 'x'

C Traversal would continue normally and return prefixCount at 'e'

D Traversal would skip the missing character and continue

💡 Hint

Refer to the 'Child Exists?' and 'Action' columns for missing child cases in execution_table.

Concept Snapshot

Count Words with Given Prefix in Trie:
- Start at root node
- For each prefix char, move to child node
- If child missing, return 0
- After last char, return prefixCount stored
- prefixCount = number of words sharing that prefix

Full Transcript

To count words with a given prefix in a trie, start at the root node and follow each character of the prefix. If at any point the child node for a character does not exist, return zero because no words have that prefix. If all characters exist, after the last character, return the prefixCount stored at that node. This count tells how many words start with the prefix. The code traverses nodes for each prefix character and returns the stored count. The execution table shows each step moving through nodes for characters 'a', 'p', 'p', 'l', 'e' and finally returning the count 1. Variables track the current node and prefixCount at each step. Key moments clarify why missing children return zero and why prefixCount is returned at the last node. The visual quiz tests understanding of node traversal and missing child handling.

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. Count the total number of words in a list

C. Find the longest word in a list

D. Replace the prefix in all words with another string

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words start with a given prefix from a list of words.

2. Step 2: Identify the key operation

   We need to check each word and count those that begin with the prefix.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Counting all words instead of only those with prefix
• Looking for longest word instead of counting
• Replacing prefix instead of counting

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

easy

A. if (word.compare(pref) == 1) { /* starts with prefix */ }

B. if (word == pref) { /* starts with prefix */ }

C. if (word.substr(1, pref.size()) == pref) { /* starts with prefix */ }

D. if (word.find(pref) == 0) { /* starts with prefix */ }

Solution

1. Step 1: Understand string::find usage

   Using word.find(pref) == 0 checks if pref is found at the start (index 0) of word.

2. Step 2: Check other options

   if (word == pref) { /* starts with prefix */ } checks equality, not prefix. if (word.substr(1, pref.size()) == pref) { /* starts with prefix */ } checks substring starting at index 1, which is wrong. if (word.compare(pref) == 1) { /* starts with prefix */ } compares strings but result 1 means greater, not prefix.

3. Final Answer:

   if (word.find(pref) == 0) { /* starts with prefix */ } -> Option D

4. Quick Check:

   find(pref) == 0 means prefix match [OK]

Hint: Use find(pref) == 0 to check prefix in C++ strings [OK]

Common Mistakes:

• Using equality instead of prefix check
• Checking substring from wrong index
• Misunderstanding compare() return values

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

std::vector words = {"apple", "app", "application", "banana"};
std::string prefix = "app";
int count = 0;
for (const auto& w : words) {
    if (w.find(prefix) == 0) {
        count++;
    }
}
std::cout << count << std::endl;

medium

A. 3

B. 2

C. 1

D. 4

Solution

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

   "apple" starts with "app" (count=1), "app" starts with "app" (count=2), "application" starts with "app" (count=3), "banana" does not.

2. Step 2: Count total matches

   Total words starting with "app" are 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Words starting with "app" = 3 [OK]

Hint: Count words where find(prefix) == 0 inside loop [OK]

Common Mistakes:

• Counting words that contain prefix anywhere
• Off-by-one errors in counting
• Ignoring words that exactly equal prefix

4. Identify the error in this C++ code snippet that tries to count words starting with prefix pref:

int count = 0;
for (auto w : words) {
    if (w.find(pref)) {
        count++;
    }
}

medium

A. The count variable should be initialized to -1

B. The loop variable should be a reference: auto& w

C. The condition should check if w.find(pref) == 0, not just w.find(pref)

D. The find function should be replaced with substr

Solution

1. Step 1: Understand find() return value

   find() returns position or npos. Using if(w.find(pref)) treats 0 as false, so words starting at index 0 are skipped.

2. Step 2: Correct condition for prefix check

   We must check if w.find(pref) == 0 to confirm prefix at start.

3. Final Answer:

   The condition should check if w.find(pref) == 0, not just w.find(pref) -> Option C

4. Quick Check:

   Check find() == 0 for prefix [OK]

Hint: Always compare find() result to 0 for prefix check [OK]

Common Mistakes:

• Using if(w.find(pref)) which fails for prefix at start
• Not using reference in loop (less critical here)
• Initializing count incorrectly

5. Given a list of words and a prefix, how would you efficiently count words starting with the prefix if the list is very large and queried multiple times?
Choose the best approach.

hard

A. Check each word with find(prefix) == 0 every time a query comes

B. Use a Trie (prefix tree) to store words and count prefix matches quickly

C. Sort the list and use binary search to find prefix range each time

D. Store words in a hash set and check prefix membership

Solution

1. Step 1: Understand repeated prefix queries

   Checking each word every time is slow for large lists and many queries.

2. Step 2: Use Trie data structure

   A Trie stores words by prefixes, allowing fast counting of words with given prefix in O(length of prefix) time.

3. Step 3: Evaluate other options

   Binary search after sorting helps but is less efficient for many queries. Hash set doesn't support prefix queries efficiently.

4. Final Answer:

   Use a Trie (prefix tree) to store words and count prefix matches quickly -> Option B

5. Quick Check:

   Trie = fast prefix counting [OK]

Hint: Use Trie for fast repeated prefix counts [OK]

Common Mistakes:

• Checking all words each query (slow)
• Using hash set which doesn't support prefix queries
• Ignoring Trie advantages for prefix problems