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 exists in children

↓

Move to child

↓

Repeat for next char

↓

Count words under current node

↓

Return count

Traverse the trie following each character of the prefix. If all characters exist, count words below the last node.

Execution Sample

DSA C

int countPrefix(struct TrieNode* root, const char* prefix) {
    struct TrieNode* node = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (!node->children[index]) return 0;
        node = node->children[index];
    }
    return node->countWordsBelow;
}

This code counts how many words in the trie start with the given prefix.

Execution Table

Step	Operation	Current Char	Node Exists?	Action	Words Counted	Visual State
1	Start at root	-	Yes	Set node = root	N/A	root
2	Check prefix char 'c'	c	Yes	Move to child 'c'	N/A	root -> c
3	Check prefix char 'a'	a	Yes	Move to child 'a'	N/A	root -> c -> a
4	Check prefix char 't'	t	Yes	Move to child 't'	N/A	root -> c -> a -> t
5	Prefix end reached	-	N/A	Return countWordsBelow at 't'	2	root -> c -> a -> t (count=2)
6	End	-	-	-	-	Count returned: 2

💡 Prefix fully matched; counted words below last node.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
node	root	node at 'c'	node at 'a'	node at 't'	node at 't'
current char	-	'c'	'a'	't'	-
words count	-	-	-	-	2

Key Moments - 2 Insights

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

Because if any character in the prefix is missing in the trie (see step 3 or 4 in execution_table), no word can start with that prefix.

Why do we count words below the last prefix node instead of counting all nodes?

Because only words that start with the prefix are stored under the last prefix node (step 5). Counting all nodes would include unrelated words.

Visual Quiz - 3 Questions

Look at the execution_table, what is the node after checking the prefix character 'a'?

A node at 't'

B node at 'a'

C node at 'c'

D root node

💡 Hint

Check the 'node' variable in variable_tracker after Step 3.

At which step does the function return the count of words with the prefix?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Action' column in execution_table where countWordsBelow is returned.

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

A Return 0 because 'r' child does not exist

B Move to child 'r'

C Count words below 'a'

D Return countWordsBelow at 't'

💡 Hint

Refer to the 'Node Exists?' and 'Action' columns in execution_table for missing nodes.

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 countWordsBelow
- countWordsBelow tracks words under node
- Efficient prefix search in O(length of prefix)

Full Transcript

To count words with a given prefix in a trie, start at the root node. For each character in the prefix, check if the child node exists. If any character node is missing, return zero because no words start with that prefix. If all characters exist, move down the trie nodes. After the last prefix character, return the count of words stored below that node. This count represents how many words start with the prefix. The code example shows a loop over prefix characters, moving the node pointer, and returning the countWordsBelow value. The execution table traces each step, showing node moves and final count returned. Key moments clarify why missing nodes cause zero return and why counting below the last node is correct. The visual quiz tests understanding of node positions and return steps. This method efficiently counts prefix words in time proportional to prefix length.

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 given prefix

B. Count the total number of characters in all words

C. Find the longest word in the list

D. Sort the words alphabetically

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words start with a specific prefix string.

2. Step 2: Identify the key operation

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Look for words starting exactly with the prefix [OK]

Common Mistakes:

• Counting total characters instead of words
• Looking for words containing prefix anywhere
• Sorting words instead of counting

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

easy

A. strcmp(word, prefix) == 0

B. strncmp(word, prefix, strlen(prefix)) == 0

C. strstr(word, prefix) != NULL

D. strlen(word) == strlen(prefix)

Solution

1. Step 1: Understand string comparison functions

   strncmp compares first n characters; here n = length of prefix.

2. Step 2: Check which code confirms prefix match

   strncmp(word, prefix, strlen(prefix)) == 0 means word starts with prefix exactly.

3. Final Answer:

   strncmp(word, prefix, strlen(prefix)) == 0 -> Option B

4. Quick Check:

   strncmp with prefix length = 0 means prefix match [OK]

Hint: Use strncmp with prefix length to check start [OK]

Common Mistakes:

• Using strcmp which requires full string match
• Using strstr without checking start position
• Comparing lengths only

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

char *words[] = {"apple", "app", "application", "banana"};
char prefix[] = "app";
int count = 0;
for (int i = 0; i < 4; i++) {
  if (strncmp(words[i], prefix, strlen(prefix)) == 0) {
    count++;
  }
}
printf("%d\n", count);

medium

A. 4

B. 2

C. 1

D. 3

Solution

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

   "apple" starts with "app" (yes), "app" (yes), "application" (yes), "banana" (no).

2. Step 2: Count matching words

   Three words match the prefix, so count = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Words starting with "app" = 3 [OK]

Hint: Count words where strncmp returns 0 for prefix length [OK]

Common Mistakes:

• Counting words that contain prefix anywhere
• Off-by-one errors in loop
• Incorrect prefix length in strncmp

4. Find the bug in this C code that counts words starting with prefix prefix:

int countWords(char *words[], int n, char *prefix) {
  int count = 0;
  for (int i = 0; i <= n; i++) {
    if (strncmp(words[i], prefix, strlen(prefix)) == 0) {
      count++;
    }
  }
  return count;
}

medium

A. Initialize count to 1 instead of 0

B. Use strcmp instead of strncmp

C. Loop condition should be i < n, not i <= n

D. strlen(prefix) should be replaced with strlen(words[i])

Solution

1. Step 1: Analyze loop boundary

   Loop runs from i = 0 to i <= n, which accesses words[n] (out of bounds).

2. Step 2: Correct loop condition

   Change to i < n to avoid accessing beyond array size.

3. Final Answer:

   Loop condition should be i < n, not i <= n -> Option C

4. Quick Check:

   Array index must be less than size [OK]

Hint: Use i < n for array loops to avoid overflow [OK]

Common Mistakes:

• Using <= instead of < in loops
• Confusing strcmp and strncmp usage
• Wrong length argument in strncmp

5. You have a list of words and want to count how many start with prefix pre. Which approach is best to optimize counting if you must do many prefix queries efficiently?

hard

A. Build a trie (prefix tree) from words and count nodes matching prefix

B. Use strncmp on each word for every query

C. Sort words and use binary search for prefix range

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

Solution

1. Step 1: Understand multiple prefix queries

   Checking each word with strncmp repeatedly is slow for many queries.

2. Step 2: Choose data structure for fast prefix counting

   Trie stores words by prefixes, allowing quick count of words with given prefix.

3. Step 3: Compare alternatives

   Binary search helps but trie is more direct for prefix counts; hash set doesn't support prefix queries well.

4. Final Answer:

   Build a trie (prefix tree) from words and count nodes matching prefix -> Option A

5. Quick Check:

   Trie = fast prefix count [OK]

Hint: Use trie for fast multiple prefix queries [OK]

Common Mistakes:

• Using linear search for many queries
• Ignoring trie benefits for prefix problems
• Using hash set which doesn't support prefix search