Count Words with Given Prefix in DSA Rust - Execution Trace

Concept Flow - Count Words with Given Prefix

Start at root node

↓

For each char in prefix

↓

Check if char exists in children

↓

Move to child

↓

Repeat for next char

↓

Count words under current node

↓

Return count

Start from the root of the trie, follow each character of the prefix. If all characters exist, count words below the last node.

Execution Sample

DSA Rust

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, Box<TrieNode>>,
    count: usize,
}

fn count_prefix(root: &TrieNode, prefix: &str) -> usize {
    let mut node = root;
    for ch in prefix.chars() {
        if let Some(next) = node.children.get(&ch) {
            node = &*next;
        } else {
            return 0;
        }
    }
    node.count
}

This code counts how many words in the trie start with the given prefix by traversing nodes for each prefix character.

Execution Table

Step	Operation	Current Char	Node Found?	Pointer Changes	Trie State (Visual)
1	Start at root	-	Yes	node = root	root {a->node1, b->node2}, count=0
2	Check 'a'	a	Yes	node = node1	node1 {p->node3}, count=2
3	Check 'p'	p	Yes	node = node3	node3 {p->node4}, count=2
4	Check 'p'	p	Yes	node = node4	node4 {l->node5}, count=1
5	Check 'l'	l	Yes	node = node5	node5 {e->node6}, count=1
6	Check 'e'	e	Yes	node = node6	node6 {}, count=1
7	Prefix fully matched	-	-	-	Count at node6 = 1
8	Return count	-	-	-	Result = 1
9	Check prefix 'apx'	x	No	-	Return 0

💡 Traversal stops when prefix fully matched or character not found in children.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
node	root	node1	node3	node4	node5	node6	node6
current_char	-	a	p	p	l	e	-
count	-	-	-	-	-	-	1

Key Moments - 2 Insights

Why do we return 0 immediately if a character is not found in children?

Because if any character of the prefix is missing, no word in the trie can start with that prefix. See execution_table row 9 where 'x' is not found.

Why do we return the count at the last node after matching the prefix?

The count at the last node represents how many words have that prefix. This is shown in execution_table row 7 and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which node does the pointer move to?

A node3

B node4

C node5

D root

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table.

At which step does the prefix fully match in the trie?

A Step 7

B Step 6

C Step 5

D Step 8

💡 Hint

Look for the row where 'Prefix fully matched' is mentioned in execution_table.

If the prefix was 'apx', what would be the returned count?

A 1

B 2

C 0

D Undefined

💡 Hint

See execution_table row 9 where 'x' is not found and count returned is 0.

Concept Snapshot

Count Words with Given Prefix in Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If any char missing, return 0
- After full prefix match, return count at last node
- Count stores how many words share that prefix

Full Transcript

To count words with a given prefix in a trie, start at the root node. For each character in the prefix, check if it exists in the current node's children. If it does, move to that child node. If any character is missing, return zero immediately because no words have that prefix. Once all prefix characters are matched, return the count stored at the last node, which represents how many words start with that prefix. This process efficiently finds the count by traversing only the prefix path in the trie.

Practice

1. What does the problem "Count Words with Given Prefix" ask you to do?

easy

A. Find the longest word in a list

B. Count how many words in a list start with a specific prefix

C. Count the total number of characters in all words

D. Sort the words alphabetically

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words start with a given prefix, not about length or sorting.

2. Step 2: Identify the key task

   Counting words that begin with the prefix is the main task.

3. Final Answer:

   Count how many words in a list start with a specific prefix -> Option B

4. Quick Check:

   Count words starting with prefix = Count how many words in a list start with a specific prefix [OK]

Hint: Focus on words starting with prefix, not full word or sorting [OK]

Common Mistakes:

• Confusing prefix with substring anywhere in word
• Counting total characters instead of words
• Sorting words instead of counting

2. Which of the following Rust code snippets correctly checks if a word starts with a given prefix prefix?

easy

A. word.starts_with(prefix)

B. word.contains(prefix)

C. word.ends_with(prefix)

D. word == prefix

Solution

1. Step 1: Recall Rust string methods

   Rust's starts_with method checks if a string begins with a given substring.

2. Step 2: Compare options

   contains checks anywhere, ends_with checks suffix, and == checks full equality, so only starts_with fits.

3. Final Answer:

   word.starts_with(prefix) -> Option A

4. Quick Check:

   Use starts_with() to check prefix [OK]

Hint: Use starts_with() method to check prefix in Rust strings [OK]

Common Mistakes:

• Using contains() which matches anywhere, not just prefix
• Using ends_with() which checks suffix
• Comparing full equality instead of prefix

3. What is the output of this Rust code?

let words = vec!["apple", "app", "application", "banana"];
let prefix = "app";
let count = words.iter().filter(|w| w.starts_with(prefix)).count();
println!("{}", count);

medium

A. 3

B. 2

C. 1

D. 4

Solution

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

   Words are "apple", "app", "application", and "banana". The first three start with "app".

2. Step 2: Count matching words

   Count is 3 because "apple", "app", and "application" start with "app".

3. Final Answer:

   3 -> Option A

4. Quick Check:

   3 words start with "app" [OK]

Hint: Count words where starts_with(prefix) is true [OK]

Common Mistakes:

• Counting only exact matches
• Including words that don't start with prefix
• Off-by-one counting errors

4. The following Rust code tries to count words starting with a prefix but gives wrong output. What is the bug?

let words = vec!["cat", "car", "dog", "scare"];
let prefix = "car";
let count = words.iter().filter(|w| w.contains(prefix)).count();
println!("{}", count);

medium

A. Missing semicolon after count declaration

B. Prefix variable is not declared correctly

C. The vector words is empty

D. Using contains() instead of starts_with() causes wrong matches

Solution

1. Step 1: Understand difference between contains() and starts_with()

   contains() checks if prefix appears anywhere, not just at start.

2. Step 2: Identify incorrect matches

   "scare" contains "car" but does not start with "car", so contains() wrongly counts it.

3. Final Answer:

   Using contains() instead of starts_with() causes wrong matches -> Option D

4. Quick Check:

   Use starts_with() to count prefix matches [OK]

Hint: Replace contains() with starts_with() to fix prefix counting [OK]

Common Mistakes:

• Confusing contains() with starts_with()
• Assuming contains() only matches prefix
• Ignoring method differences

5. Given a list of words ["test", "tester", "testing", "toast", "team"] and prefix "te", which Rust code correctly counts words starting with the prefix and ignores case sensitivity?

hard

A. words.iter().filter(|w| w.contains(prefix)).count()

B. words.iter().filter(|w| w.starts_with(prefix)).count()

C. words.iter().filter(|w| w.to_lowercase().starts_with(&prefix.to_lowercase())).count()

D. words.iter().filter(|w| w.ends_with(prefix)).count()

Solution

1. Step 1: Understand case sensitivity in Rust strings

   Rust's starts_with is case sensitive, so we convert both word and prefix to lowercase.

2. Step 2: Check each option for case-insensitive prefix check

   words.iter().filter(|w| w.to_lowercase().starts_with(&prefix.to_lowercase())).count() converts both to lowercase before checking prefix, ensuring case-insensitive match. Others do not handle case.

3. Final Answer:

   words.iter().filter(|w| w.to_lowercase().starts_with(&prefix.to_lowercase())).count() -> Option C

4. Quick Check:

   Convert both strings to lowercase before starts_with() [OK]

Hint: Lowercase both word and prefix before starts_with() for case-insensitive [OK]

Common Mistakes:

• Ignoring case sensitivity in starts_with()
• Using contains() which is wrong for prefix
• Using ends_with() instead of starts_with()