Count Words with Given Prefix in DSA Go - Execution Trace

Concept Flow - Count Words with Given Prefix

Start at root node

↓

For each character in prefix

↓

Check if character exists in children

↓

Move to child

↓

Repeat for next char

↓

Count words from current node

↓

Return count

Start from the root of the trie, follow each character of the prefix. If all characters exist, count words below the last node.

Execution Sample

DSA Go

func countWordsWithPrefix(root *TrieNode, prefix string) int {
    node := root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return 0
        }
        node = node.children[ch]
    }
    return countWords(node)
}

This code finds the node matching the prefix and counts all words under it.

Execution Table

Step	Operation	Current Character	Node Visited	Pointer Changes	Visual State
1	Start at root	-	root	node = root	root
2	Check prefix char 'c'	c	root	node = root.children['c']	root -> c
3	Check prefix char 'a'	a	c	node = c.children['a']	root -> c -> a
4	Check prefix char 't'	t	a	node = a.children['t']	root -> c -> a -> t
5	Prefix found, count words	-	t	countWords(t)	root -> c -> a -> t (count words)
6	Count word at 't' node	-	t	-	1 word found ("cat")
7	Count word at 't' children	-	t.children	-	No children with words
8	Return total count	-	t	-	Total words with prefix "cat": 1
9	End	-	-	-	Execution complete

💡 All prefix characters found, counted words under last node.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
node	root	root.children['c']	c.children['a']	a.children['t']	t	t
current character	-	'c'	'a'	't'	-	-
count	0	0	0	0	1	1

Key Moments - 3 Insights

Why do we return 0 if a prefix character is missing?

Because if any character in the prefix is missing in the trie (see Step 2-4 in execution_table), no word can have that prefix.

How do we count words under the prefix node?

We recursively count all words that end at the current node and its children (see Step 5-7).

Why do we move the 'node' pointer at each prefix character?

To follow the path of the prefix in the trie, ensuring we reach the node representing the prefix end (see pointer changes in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the node visited at Step 3?

A root

B c

C a

D t

💡 Hint

Check the 'Node Visited' column at Step 3 in execution_table.

At which step does the code confirm the prefix is fully found?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look for the step where counting words starts after prefix traversal.

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

A return 0 because 'r' child missing

B node moves to 't' child

C node moves to 'r' child

D countWords called immediately

💡 Hint

Refer to the condition where prefix character is missing in execution_table Steps 2-4.

Concept Snapshot

Count Words with Given Prefix in Trie:
- Start at root node
- For each prefix char, move to child node
- If missing char, return 0
- After prefix, count all words below
- Counting includes current node if word ends here
- Returns total words with that 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 character exists among the current node's children. If it does, move the pointer to that child node. If any character is missing, return zero immediately because no words have that prefix. Once all prefix characters are found, count all words that end at or below the current node. This count includes the current node if it marks the end of a word. The final count is the number of words with the given prefix.

Practice

1. What does the problem "Count Words with Given Prefix" ask you to do?

easy

A. Count the total number of characters in all words

B. Find the longest word in a list

C. Count how many words in a list start with a specific prefix

D. Sort the words alphabetically

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words begin with a given prefix string.

2. Step 2: Identify the key operation

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

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing prefix with substring anywhere in word
• Counting total words instead of filtered ones
• Ignoring case sensitivity if required

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

easy

A. strings.HasPrefix(word, pref)

B. strings.Contains(word, pref)

C. word[:len(pref)] == pref

D. word == pref

Solution

1. Step 1: Recall Go standard library functions

   strings.HasPrefix(word, pref) returns true if word starts with pref.

2. Step 2: Compare other options

   strings.Contains checks anywhere, slicing may panic if prefix longer, equality checks full word.

3. Final Answer:

   strings.HasPrefix(word, pref) -> Option A

4. Quick Check:

   Use HasPrefix for prefix check [OK]

Hint: Use strings.HasPrefix for safe prefix check [OK]

Common Mistakes:

• Using strings.Contains which checks anywhere in word
• Slicing without length check causing runtime panic
• Comparing whole word instead of prefix

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

package main
import (
  "fmt"
  "strings"
)
func countPrefix(words []string, prefix string) int {
  count := 0
  for _, w := range words {
    if strings.HasPrefix(w, prefix) {
      count++
    }
  }
  return count
}
func main() {
  words := []string{"apple", "app", "application", "banana", "apply"}
  fmt.Println(countPrefix(words, "app"))
}

medium

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Identify words starting with "app"

   Words: "apple", "app", "application", "banana", "apply". "banana" does not start with "app".

2. Step 2: Count matching words

   Matching words: "apple", "app", "application", "apply" -> 4 words.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count of words starting with "app" = 4 [OK]

Hint: Count words starting exactly with prefix using HasPrefix [OK]

Common Mistakes:

• Counting "banana" incorrectly
• Off-by-one error in counting
• Misreading prefix length

4. The following Go code is intended to count words starting with a prefix but causes a runtime error. What is the error?

func countPrefix(words []string, prefix string) int {
  count := 0
  for _, w := range words {
    if w[:len(prefix)] == prefix {
      count++
    }
  }
  return count
}

medium

A. No error, code works fine

B. Index out of range panic if word shorter than prefix

C. Logical error: counts words containing prefix anywhere

D. Syntax error due to missing import

Solution

1. Step 1: Analyze slicing operation

   The code slices w[:len(prefix)] without checking if w is long enough.

2. Step 2: Identify runtime error cause

   If w is shorter than prefix, slicing causes index out of range panic.

3. Final Answer:

   Index out of range panic if word shorter than prefix -> Option B

4. Quick Check:

   Slicing without length check causes panic [OK]

Hint: Check word length before slicing prefix [OK]

Common Mistakes:

• Ignoring length check before slicing
• Assuming code compiles without imports
• Confusing prefix check with substring check

5. You have a list of words and want to count how many start with each prefix from a list of prefixes. Which approach is best for efficient counting in Go?

hard

A. Use strings.Contains to check prefix in each word

B. For each prefix, loop over all words and count matches

C. Sort words and use binary search for each prefix

D. Build a trie from words, then query counts for each prefix

Solution

1. Step 1: Understand the problem scale

   Counting for many prefixes over many words needs efficiency.

2. Step 2: Compare approaches

   Looping over all words for each prefix is slow (O(P*W)). Sorting + binary search helps but trie allows prefix counting efficiently.

3. Step 3: Choose best data structure

   Trie stores words by prefix, enabling fast prefix count queries.

4. Final Answer:

   Build a trie from words, then query counts for each prefix -> Option D

5. Quick Check:

   Trie enables efficient prefix counting [OK]

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

Common Mistakes:

• Using nested loops causing slow performance
• Using strings.Contains which is incorrect for prefix
• Ignoring data structure benefits