Count Words with Given Prefix in DSA Python - Execution Trace

Concept Flow - Count Words with Given Prefix

Start with empty Trie

↓

Insert each word

↓

For each character in word

↓

If char node missing, create it

↓

Move to char node, increment prefix count

↓

After all words inserted

↓

Search prefix

↓

Traverse prefix chars

↓

If prefix node found, return count

↓

Else return 0

Build a Trie by inserting words, counting prefixes at each node, then traverse prefix to get count.

Execution Sample

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

Defines TrieNode with children and count, and Trie with root node.

Execution Table

Step	Operation	Current Word/Prefix	Node Created	Prefix Count Updated	Visual State
1	Insert 'apple'	a	Node for 'a'	1	root -> a(1)
2	Insert 'apple'	p	Node for 'p'	1	root -> a(1) -> p(1)
3	Insert 'apple'	p	Node for 'p'	1	root -> a(1) -> p(1) -> p(1)
4	Insert 'apple'	l	Node for 'l'	1	root -> a(1) -> p(1) -> p(1) -> l(1)
5	Insert 'apple'	e	Node for 'e'	1	root -> a(1) -> p(1) -> p(1) -> l(1) -> e(1)
6	Insert 'app'	a	No new node	2	root -> a(2) -> p(1) -> p(1) -> l(1) -> e(1)
7	Insert 'app'	p	No new node	2	root -> a(2) -> p(2) -> p(1) -> l(1) -> e(1)
8	Insert 'app'	p	No new node	2	root -> a(2) -> p(2) -> p(2) -> l(1) -> e(1)
9	Insert 'bat'	b	Node for 'b'	1	root -> a(2) -> p(2) -> p(2) ... and b(1)
10	Insert 'bat'	a	Node for 'a'	1	root -> ... b(1) -> a(1)
11	Insert 'bat'	t	Node for 't'	1	root -> ... b(1) -> a(1) -> t(1)
12	Count prefix 'app'	a	No new node	N/A	Traverse nodes a(2) -> p(2) -> p(2)
13	Count prefix 'app'	p	No new node	N/A	Traverse nodes p(2) -> p(2)
14	Count prefix 'app'	p	No new node	N/A	Prefix count at last p node is 2
15	Return count	app	N/A	N/A	Result: 2
16	Count prefix 'ba'	b	No new node	N/A	Traverse nodes b(1) -> a(1)
17	Count prefix 'ba'	a	No new node	N/A	Prefix count at a node is 1
18	Return count	ba	N/A	N/A	Result: 1
19	Count prefix 'cat'	c	No node	N/A	Prefix not found, return 0
20	Return count	cat	N/A	N/A	Result: 0

💡 All words inserted and prefix counts returned; traversal stops when prefix node missing or end reached.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 8	After Step 11	After Step 15	After Step 20
Trie Root Children	{}	{'a': Node}	{'a': Node}	{'a': Node}	{'a': Node, 'b': Node}	{'a': Node, 'b': Node}	{'a': Node, 'b': Node}
Node 'a' Count	0	1	1	2	2	2	2
Node 'p' Count (first)	0	0	1	2	2	2	2
Node 'p' Count (second)	0	0	1	2	2	2	2
Node 'b' Count	0	0	0	0	1	1	1
Node 'a' Count under 'b'	0	0	0	0	1	1	1

Key Moments - 3 Insights

Why does the prefix count increase even when no new node is created?

Because prefix count tracks how many words pass through a node, so even existing nodes increment count when a new word shares that prefix (see steps 6-8 in execution_table).

What happens if the prefix is not found in the Trie?

Traversal stops when a character node is missing, and the count returned is 0 (see steps 19-20 in execution_table).

Why do we increment count at each node during insertion?

Incrementing count at each node helps quickly find how many words share that prefix without searching all words (see steps 1-5).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the prefix count at the second 'p' node?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Prefix Count Updated' column at step 8 in execution_table.

At which step does the Trie first create a node for the letter 'b'?

A Step 6

B Step 9

C Step 12

D Step 1

💡 Hint

Look at the 'Node Created' column for letter 'b' in execution_table.

If we insert the word 'app' again, how would the prefix count at node 'a' change after step 8?

A It would increase to 3

B It would stay 2

C It would decrease to 1

D It would reset to 0

💡 Hint

Refer to variable_tracker for 'Node a Count' after multiple insertions.

Concept Snapshot

Count Words with Given Prefix using Trie:
- Insert words char by char
- Create nodes if missing
- Increment prefix count at each node
- To count prefix, traverse prefix nodes
- Return count at last prefix node or 0 if missing

Full Transcript

We build a Trie data structure to count how many words start with a given prefix. Each node stores children nodes and a count of how many words pass through it. When inserting words, we create nodes for missing characters and increment counts at each node. To count words with a prefix, we traverse the Trie nodes for each prefix character. If all prefix nodes exist, we return the count at the last node. If any prefix node is missing, we return zero. This method efficiently counts prefix matches without scanning all words.

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