Count Words with Given Prefix in DSA Go - Deep Dive

Overview - Count Words with Given Prefix

What is it?

Counting words with a given prefix means finding how many words in a list start with certain letters. For example, if you have words like 'cat', 'car', and 'dog', and you want to count words starting with 'ca', the answer is 2. This helps quickly find groups of words sharing the same beginning. It is useful in search engines, autocomplete, and dictionaries.

Why it matters

Without a fast way to count words by prefix, searching through large lists would be slow and inefficient. Imagine typing in a search box and waiting for results because the system checks every word one by one. Counting words with prefixes speeds up this process, making apps and tools feel instant and smart. It also helps organize data in meaningful ways.

Where it fits

Before learning this, you should understand basic strings and arrays or lists. After this, you can explore more advanced data structures like tries (prefix trees) and hash maps for faster prefix searches. This topic is a stepping stone to efficient text processing and search algorithms.

Mental Model

Core Idea

Counting words with a given prefix is like quickly finding all items in a list that start with the same beginning letters without checking each one fully every time.

Think of it like...

It's like looking for all books on a shelf that start with the letter 'A' by going directly to the 'A' section instead of scanning every book from start to end.

Words List:
[cat, car, dog, cart, cap]
Prefix: 'ca'

Check each word:
 cat  -> starts with 'ca' -> count +1
 car  -> starts with 'ca' -> count +1
 dog  -> no
 cart -> starts with 'ca' -> count +1
 cap  -> starts with 'ca' -> count +1

Total count = 4

Build-Up - 6 Steps

1

Foundation

Understanding Prefixes in Words

Concept: What a prefix is and how to check if a word starts with it.

A prefix is the beginning part of a word. For example, 'pre' is a prefix of 'prefix'. To check if a word starts with a prefix, compare the first letters of the word with the prefix letters one by one. If all match, the word has that prefix.

Result

You can tell if a word starts with a prefix by comparing letters from the start.

Understanding prefixes is the base for counting words that share beginnings.

2

Foundation

Simple Counting by Checking Each Word

Concept: Count words by checking each word's prefix one by one.

Given a list of words and a prefix, loop through each word. For each word, check if it starts with the prefix. If yes, increase a counter by one. At the end, the counter shows how many words start with that prefix.

Result

A number representing how many words start with the prefix.

This method works but can be slow for large lists because it checks every word.

3

Intermediate

Using a Trie for Efficient Prefix Counting

🤔Before reading on: Do you think checking every word is the fastest way to count prefixes? Commit to yes or no.

Concept: A trie is a tree-like structure that stores words by their letters, allowing fast prefix queries.

A trie stores words by breaking them into letters and linking nodes for each letter. Each node can keep track of how many words pass through it. To count words with a prefix, follow the prefix letters down the trie. The node at the end of the prefix holds the count of words starting with it.

Result

Counting prefix words becomes fast, even for large word lists.

Using tries avoids checking every word by organizing words by their letters.

4

Intermediate

Building a Trie with Word Counts

🤔Before reading on: Do you think each node in a trie should store how many words pass through it? Commit to yes or no.

Concept: Each trie node stores a count of words passing through to enable quick prefix counts.

When inserting a word into a trie, for each letter, move to the child node or create it if missing. Increase the count at each node by one to record how many words include that letter path. This way, the count at the node representing the prefix end tells how many words start with that prefix.

Result

A trie where each node knows how many words share its prefix path.

Storing counts at nodes lets us answer prefix queries instantly.

5

Advanced

Implementing Prefix Count Query in Trie

🤔Before reading on: When searching a prefix in a trie, do you think you must check all words or just follow the prefix path? Commit to your answer.

Concept: To count words with a prefix, follow the prefix path in the trie and read the stored count.

To count words with a prefix, start at the root node. For each letter in the prefix, move to the child node matching that letter. If at any point the child node does not exist, return zero because no words have that prefix. If you reach the last prefix letter, return the count stored at that node.

Result

Fast retrieval of how many words start with the prefix.

Following the prefix path directly avoids scanning unrelated words.

6

Expert

Optimizing Trie Memory and Performance

🤔Before reading on: Do you think tries always use less memory than simple lists? Commit to yes or no.

Concept: Tries can be optimized by compressing nodes and careful memory use to balance speed and space.

Tries can consume a lot of memory if each node stores many children. To optimize, use techniques like compressing chains of single-child nodes into one node (called a radix trie), or using arrays or hash maps only when needed. These reduce memory while keeping fast prefix queries. Also, storing counts only at necessary nodes saves space.

Result

A trie that is both fast and memory-efficient for prefix counting.

Knowing trie optimizations helps build scalable systems handling millions of words.

Under the Hood

A trie works by creating a tree where each node represents a letter. Words are paths from the root to leaf nodes. Each node keeps a count of how many words pass through it. When counting words with a prefix, the trie follows the prefix letters down the tree and returns the count stored at the last node. This avoids scanning all words and uses the tree structure to jump directly to relevant words.

Why designed this way?

Tries were designed to speed up prefix searches by organizing words by their letters. Before tries, searching prefixes meant checking every word, which is slow for large data. Tries trade extra memory for much faster queries. Alternatives like hash maps don't support prefix queries efficiently, so tries fill this gap.

Root
 ├─ c (count=4)
 │   ├─ a (count=4)
 │   │   ├─ t (count=1)
 │   │   ├─ r (count=2)
 │   │   └─ p (count=1)
 └─ d (count=1)
     └─ o (count=1)
         └─ g (count=1)

Prefix 'ca' path: Root -> c -> a (count=4)
Count at 'a' node = 4 means 4 words start with 'ca'

Myth Busters - 3 Common Misconceptions

Quick: Does counting words with a prefix always require checking every word? Commit yes or no.

Common Belief: You must check every word in the list to count how many start with a prefix.

Reality: Using a trie, you can count words with a prefix by following the prefix path and reading a stored count, without checking all words.

Why it matters: Believing you must check every word leads to slow programs that don't scale to large datasets.

Quick: Do tries always use less memory than simple lists? Commit yes or no.

Common Belief: Tries always use less memory than storing words in a list.

Reality: Tries often use more memory because they store nodes for each letter and pointers, but they speed up prefix queries.

Why it matters: Ignoring memory cost can cause programs to run out of memory or be inefficient on devices with limited resources.

Quick: Does storing counts only at leaf nodes work for prefix counting? Commit yes or no.

Common Belief: Counting words with a prefix only needs counts at the end of full words (leaf nodes).

Reality: Counts must be stored at every node along the path to quickly answer prefix queries, not just at leaves.

Why it matters: Storing counts only at leaves makes prefix queries slow or impossible without scanning.

Expert Zone

1

Trie nodes can store counts of words ending exactly at that node versus words passing through, enabling different query types.

2

Balancing trie depth and branching factor affects performance; shallow tries with large branching can be faster but use more memory.

3

Combining tries with other data structures like hash maps at nodes can optimize speed and memory depending on data distribution.

When NOT to use

If the dataset is small or prefix queries are rare, simple linear search or sorting with binary search may be better. For very large alphabets or memory-constrained environments, compressed tries or suffix arrays might be preferred.

Production Patterns

Tries are used in autocomplete systems, spell checkers, IP routing tables, and DNA sequence analysis. Production systems often combine tries with caching and compression to handle millions of entries efficiently.

Connections

Trie (Prefix Tree)

Builds-on

Understanding counting words with prefixes is a direct application of tries, which organize words by letters for fast prefix queries.

Binary Search

Alternative approach

Sorted word lists allow prefix counting by binary searching prefix start and end positions, showing different tradeoffs between tries and binary search.

Database Indexing

Similar pattern

Counting words with prefixes is like database indexing on text columns, where indexes speed up prefix or range queries on large datasets.

Common Pitfalls

#1 Checking every word for prefix in large lists causes slow performance.

Wrong approach:

for _, word := range words {
if strings.HasPrefix(word, prefix) {
count++
}
}
// This loops through all words every time.

Correct approach:

Build a trie once with all words.
Then, for each prefix query, follow the prefix path in the trie and return the stored count.

Root cause:

Not using data structures that support fast prefix queries leads to repeated full scans.

#2 Storing counts only at leaf nodes prevents fast prefix counting.

Wrong approach:

type TrieNode struct {
children map[rune]*TrieNode
isWord bool
// No count field here
}
// Counting prefix requires scanning subtree.

Correct approach:

type TrieNode struct {
children map[rune]*TrieNode
count int // number of words passing through
isWord bool
}
// Increment count during insertion to enable fast prefix count.

Root cause:

Misunderstanding that counts must be stored at every node along prefix paths.

#3 Not handling missing prefix nodes returns wrong counts.

Wrong approach:

func CountPrefix(root *TrieNode, prefix string) int {
node := root
for _, ch := range prefix {
node = node.children[ch]
}
return node.count
}
// This panics if prefix not found.

Correct approach:

func CountPrefix(root *TrieNode, prefix string) int {
node := root
for _, ch := range prefix {
next, ok := node.children[ch]
if !ok {
return 0
}
node = next
}
return node.count
}

Root cause:

Not checking for missing nodes causes runtime errors.

Key Takeaways

Counting words with a given prefix helps quickly find how many words start with certain letters without scanning all words every time.

A trie is a tree structure that stores words by letters and keeps counts at each node to enable fast prefix counting.

Building a trie involves inserting words letter by letter and updating counts at each node along the path.

Prefix queries follow the prefix path in the trie and return the stored count, making queries very fast even for large datasets.

Understanding trie optimizations and limitations helps build efficient, scalable systems for text search and autocomplete.