Count Words with Given Prefix in DSA Go

Mental Model

We want to find how many words start with a certain beginning part (prefix). We check each word to see if it begins with that prefix and count it.

Analogy: Imagine you have a box of books and you want to count how many titles start with the word 'The'. You look at each title and count only those that start with 'The'.

words: ["apple", "app", "ape", "bat", "ball"]
prefix: "ap"

We check each word:
"apple" -> starts with "ap" -> count++
"app" -> starts with "ap" -> count++
"ape" -> starts with "ap" -> count++
"bat" -> no
"ball" -> no

Dry Run Walkthrough

Input: words: ["apple", "app", "ape", "bat", "ball"], prefix: "ap"

Goal: Count how many words start with the prefix "ap"

Step 1: Check word "apple" if it starts with "ap"

"apple" starts with "ap" -> count = 1

Why: We found one word starting with the prefix

Step 2: Check word "app" if it starts with "ap"

"app" starts with "ap" -> count = 2

Why: Another word matches the prefix

Step 3: Check word "ape" if it starts with "ap"

"ape" starts with "ap" -> count = 3

Why: Another word matches the prefix

Step 4: Check word "bat" if it starts with "ap"

"bat" does not start with "ap" -> count = 3

Why: No match, count stays the same

Step 5: Check word "ball" if it starts with "ap"

"ball" does not start with "ap" -> count = 3

Why: No match, count stays the same

Result:

Final count = 3

Annotated Code

DSA Go

package main

import (
	"fmt"
	"strings"
)

// countWordsWithPrefix counts how many words start with the given prefix
func countWordsWithPrefix(words []string, prefix string) int {
	count := 0
	for _, word := range words {
		if strings.HasPrefix(word, prefix) {
			count++ // increment count when prefix matches
		}
	}
	return count
}

func main() {
	words := []string{"apple", "app", "ape", "bat", "ball"}
	prefix := "ap"
	result := countWordsWithPrefix(words, prefix)
	fmt.Println(result)
}

for _, word := range words {

iterate over each word to check prefix

if strings.HasPrefix(word, prefix) {

check if current word starts with prefix

count++ // increment count when prefix matches

increase count for each matching word

Output

3

Complexity Analysis

Time: O(n * m) because we check each of the n words and compare up to m characters of the prefix

Space: O(1) because we only use a counter variable, no extra space grows with input

vs Alternative: A trie data structure can do prefix counts faster for many queries, but building it costs extra time and space

Edge Cases

empty words list

returns 0 because no words to check

DSA Go

for _, word := range words {

empty prefix string

counts all words because every word starts with empty prefix

DSA Go

if strings.HasPrefix(word, prefix) {

no words start with prefix

returns 0 because no matches found

DSA Go

if strings.HasPrefix(word, prefix) {

When to Use This Pattern

When you need to count or find words starting with a certain beginning part, use prefix checking with string functions or tries for efficiency.

Common Mistakes

Mistake: Checking if prefix is contained anywhere in the word instead of only at the start
Fix: Use strings.HasPrefix to ensure prefix matches only at the start

Summary

Counts how many words in a list start with a given prefix.

Use when you want to filter or count words by their starting letters.

The key is to check only the start of each word, not anywhere inside.

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