Count Words with Given Prefix in DSA Python

Mental Model

We want to find how many words start with a certain beginning part (prefix). We look through all words and count those that match the start.

Analogy: Imagine a library where you want to find how many books have titles starting with 'The'. You scan the titles and count each one that begins with 'The'.

Words list:
["apple", "app", "ape", "bat", "ball"]
Prefix to find: "ap"
We check each word if it starts with "ap".

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" (match), "app", "ape", "bat", "ball"]

Why: We need to count words starting with the prefix

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

["apple" (match), "app" (match), "ape", "bat", "ball"]

Why: Continue checking all words for prefix match

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

["apple" (match), "app" (match), "ape" (match), "bat", "ball"]

Why: Count all words that start with prefix

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

["apple" (match), "app" (match), "ape" (match), "bat", "ball"]

Why: No match, skip counting

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

["apple" (match), "app" (match), "ape" (match), "bat", "ball"]

Why: No match, skip counting

Result:

Final count = 3
Words starting with "ap": apple, app, ape

Annotated Code

DSA Python

class WordPrefixCounter:
    def __init__(self, words):
        self.words = words

    def count_prefix(self, prefix):
        count = 0
        for word in self.words:
            if word.startswith(prefix):
                count += 1
        return count

# Driver code
words = ["apple", "app", "ape", "bat", "ball"]
prefix = "ap"
counter = WordPrefixCounter(words)
result = counter.count_prefix(prefix)
print(f"Number of words starting with '{prefix}': {result}")

for word in self.words:

iterate over each word to check prefix

if word.startswith(prefix):

check if current word starts with the given prefix

count += 1

increment count for each matching word

Output

Number of words starting with 'ap': 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(n) to store the list of words

vs Alternative: A trie data structure can speed up prefix counting to O(m) after building, but building the trie costs O(n * k) where k is average word length

Edge Cases

Empty words list

Returns 0 because no words to check

DSA Python

for word in self.words:

Prefix longer than any word

No words match, returns 0

DSA Python

if word.startswith(prefix):

All words match prefix

Returns total number of words

DSA Python

count += 1

When to Use This Pattern

When asked to count or find words starting with a prefix, use simple iteration and string start checks for small data or tries for large data.

Common Mistakes

Mistake: Checking if prefix is in the word anywhere instead of only at the start
Fix: Use word.startswith(prefix) to ensure prefix is at the beginning

Summary

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

Use when you need to find how many words share the same beginning letters.

The key is to check each word's start against the prefix and count matches.

Practice

1. What does the function countWordsStartingWith(words, prefix) do when given a list of words and a prefix?

easy

A. Counts how many words contain the prefix anywhere inside

B. Returns the first word that starts with the prefix

C. Counts how many words in the list start with the given prefix

D. Removes all words that start with the prefix from the list

Solution

1. Step 1: Understand the function purpose

   The function is designed to count words that begin with a specific prefix, not just contain it anywhere.

2. Step 2: Compare options with function behavior

   Only Counts how many words in the list start with the given prefix correctly describes counting words starting with the prefix. Others describe different behaviors.

3. Final Answer:

   Counts how many words in the list start with the given prefix -> Option C

4. Quick Check:

   Counting words starting with prefix = Counts how many words in the list start with the given prefix [OK]

Hint: Focus on 'start with' meaning prefix at word beginning [OK]

Common Mistakes:

• Confusing 'start with' and 'contain' prefix
• Thinking function returns words instead of count
• Assuming it removes words instead of counting

2. Which of the following Python code snippets correctly counts words starting with a prefix p in a list words?

easy

A. sum(word.startswith(p) for word in words)

B. sum(word.startswith(p) == 'True' for word in words)

C. sum(word.startswith(p) is 'True' for word in words)

D. sum(word.startswith(p) = True for word in words)

Solution

1. Step 1: Check syntax correctness

   sum(word.startswith(p) = True for word in words) uses '=' inside sum which is invalid syntax for comparison.

2. Step 2: Understand boolean summation

   Options B and C incorrectly compare boolean to string 'True' (always False). Only sum(word.startswith(p) for word in words) correctly sums booleans directly (True counts as 1).

3. Final Answer:

   sum(word.startswith(p) for word in words) -> Option A

4. Quick Check:

   Use sum with boolean directly for counting [OK]

Hint: Use sum with boolean expressions directly, no need for == or is [OK]

Common Mistakes:

• Using '=' instead of '==' for comparison
• Comparing boolean to string 'True'
• Confusing syntax causing errors

3. What is the output of the following code?

words = ['apple', 'app', 'application', 'banana', 'apply']
prefix = 'app'
count = sum(word.startswith(prefix) for word in words)
print(count)

medium

A. 2

B. 3

C. 5

D. 4

Solution

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

   Words starting with 'app' are 'apple', 'app', 'application', and 'apply' -- total 4 words.

2. Step 2: Calculate sum of True values

   Each word starting with prefix counts as 1, so sum is 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Count words starting with 'app' = 4 [OK]

Hint: Count words starting exactly with prefix, not just containing it [OK]

Common Mistakes:

• Counting words that contain prefix anywhere
• Missing one word that starts with prefix
• Confusing prefix length with word length

4. Find the error in this code that tries to count words starting with prefix 'pre':

def count_prefix(words, prefix):
    count = 0
    for word in words:
        if word.startswith == prefix:
            count += 1
    return count

words = ['prefix', 'preach', 'prevent', 'post']
prefix = 'pre'
print(count_prefix(words, prefix))

medium

A. Using 'word.startswith == prefix' instead of 'word.startswith(prefix)'

B. Missing return statement in function

C. Incorrect variable name 'count' used

D. Loop should be 'for prefix in words' instead of 'for word in words'

Solution

1. Step 1: Identify incorrect method usage

   The code uses 'word.startswith == prefix' which compares method to string, incorrect syntax.

2. Step 2: Correct method call

   It should be 'word.startswith(prefix)' to check if word starts with prefix.

3. Final Answer:

   Using 'word.startswith == prefix' instead of 'word.startswith(prefix)' -> Option A

4. Quick Check:

   Method call needs parentheses with argument [OK]

Hint: Remember to call methods with parentheses and arguments [OK]

Common Mistakes:

• Comparing method itself instead of calling it
• Forgetting parentheses after method name
• Mixing variable names in loop

5. Given a list of words, how would you count words starting with any prefix from a list of prefixes prefixes? Choose the correct code snippet.

words = ['cat', 'car', 'dog', 'cart', 'cow']
prefixes = ['ca', 'do', 'co']

hard

A. sum(word.startswith(prefixes[0]) or word.startswith(prefixes[1]) for word in words)

B. sum(any(word.startswith(p) for p in prefixes) for word in words)

C. sum(word.startswith(prefixes) for word in words)

D. sum(word.startswith(p) and p in prefixes for word in words)

Solution

1. Step 1: Understand requirement for multiple prefixes

   We need to check if each word starts with any prefix in the prefixes list.

2. Step 2: Analyze options for correct logic

   sum(any(word.startswith(p) for p in prefixes) for word in words) uses any() to correctly check if word starts with any prefix. sum(word.startswith(prefixes[0]) or word.startswith(prefixes[1]) for word in words) only checks first two prefixes (misses 'cow' with 'co'). sum(word.startswith(prefixes) for word in words) passes list to startswith (TypeError). sum(word.startswith(p) and p in prefixes for word in words) uses unbound p and incorrect and logic.

3. Final Answer:

   sum(any(word.startswith(p) for p in prefixes) for word in words) -> Option B

4. Quick Check:

   Use any() to check multiple prefixes per word [OK]

Hint: Use any() inside sum() to check multiple prefixes per word [OK]

Common Mistakes:

• Passing list directly to startswith instead of iterating
• Using 'and' instead of 'or' logic
• Hardcoding prefix checks instead of looping