Count Words with Given Prefix in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'Count Words with Given Prefix' mean in simple terms?

It means finding how many words in a list start with the same beginning letters (prefix). For example, counting words starting with "pre" in ["prefix", "prevent", "apple"] gives 2.

intermediate

Why is a Trie (prefix tree) useful for counting words with a given prefix?

A Trie stores words so that common beginnings share nodes. This makes it fast to find all words starting with a prefix by just following the prefix path and counting words below it.

intermediate

In Go, what basic steps do you take to count words with a given prefix using a Trie?

1. Build a Trie by inserting all words.
2. Traverse the Trie following the prefix letters.
3. Count how many words are stored under that prefix node.

advanced

What is the time complexity benefit of using a Trie for prefix counting compared to checking each word?

Using a Trie, counting words with a prefix takes time proportional to the prefix length, not the total number of words. Checking each word takes time proportional to all words times prefix length.

beginner

What happens if the prefix does not exist in the Trie?

If the prefix path is missing in the Trie, it means no words start with that prefix, so the count is zero.

What data structure is best suited for counting words with a given prefix efficiently?

A HashSet

B Stack

C Trie (prefix tree)

D Queue

Trie stores words by prefixes, making prefix queries fast.

If you have 1000 words and want to count words starting with "go", what is the fastest approach?

A Use a stack to store words

B Check each word one by one

C Sort words and binary search

D Use a Trie to find prefix count

Trie allows direct prefix traversal, faster than checking all words.

What does the prefix "pre" mean when counting words?

A Words that start with "pre"

B Words that contain "pre" anywhere

C Words that end with "pre"

D Words with exactly three letters

Prefix means the start of the word.

What is the count of words with prefix "cat" in ["cat", "cater", "dog", "catalog"]?

A 3

B 1

C 2

D 4

"cat", "cater", and "catalog" all start with "cat".

If a prefix is not found in the Trie, what should the count be?

A Number of all words

B Zero

C Length of prefix

D One

No words start with that prefix, so count is zero.

Explain how a Trie helps count words with a given prefix quickly.

Think about how words with the same start share parts.

Describe the steps to count words with a given prefix using Go code and a Trie.

Focus on building and searching the Trie.

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