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.