Count Words with Given Prefix in DSA Typescript - Execution Trace

Concept Flow - Count Words with Given Prefix

Start with empty Trie

↓

Insert each word

↓

For each character in word

↓

Create node if missing

↓

Increment prefix count

↓

After all words inserted

↓

Search prefix

↓

Traverse nodes for prefix chars

↓

If prefix node found

↓

Return count stored at prefix node

↓

Else return 0

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

Execution Sample

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  count: number = 0;
}

// Insert words and count prefixes
// Query prefix count

Insert words into Trie, increment counts for prefixes, then query prefix count.

Execution Table

Step	Operation	Word/Prefix	Node Created	Prefix Count Updated	Visual State
1	Insert	"apple"	a, p, p, l, e nodes created	a:1, p:1, p:1, l:1, e:1	root -> a(1) -> p(1) -> p(1) -> l(1) -> e(1)
2	Insert	"app"	No new nodes	a:2, p:2, p:2	root -> a(2) -> p(2) -> p(2) -> l(1) -> e(1)
3	Insert	"ape"	e node created under p	a:3, p:3, e:1	root -> a(3) -> p(3) -> p(2) -> l(1) -> e(1) -> e(1)
4	Query	"ap"	No	No	Count at node 'p' after 'a' is 3
5	Query	"app"	No	No	Count at node 'p' after 'ap' is 2
6	Query	"apple"	No	No	Count at node 'e' after 'appl' is 1
7	Query	"bat"	No	No	Prefix not found, return 0

💡 All words inserted and prefix queries completed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
Trie Root	empty	a node with count 1	a node with count 2	a node with count 3	unchanged	unchanged	unchanged	unchanged
Node 'a' count	0	1	2	3	3	3	3	3
Node 'p' count (first p)	0	1	2	3	3	3	3	3
Node 'p' count (second p)	0	1	2	2	2	2	2	2
Node 'l' count	0	1	1	1	1	1	1	1
Node 'e' count (under l)	0	1	1	1	1	1	1	1
Node 'e' count (under p)	0	0	0	1	1	1	1	1

Key Moments - 3 Insights

Why do we increment the count at each node when inserting a word?

Because each node represents a prefix. Incrementing count tracks how many words share that prefix, as shown in steps 1-3 in the execution_table.

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

We return 0 immediately because no words start with that prefix, as shown in step 7 where 'bat' is not found.

Why do some nodes get created and others don't during insertion?

Nodes are created only if the character path does not exist yet. For example, in step 2 inserting 'app' no new nodes are created because 'a' and 'p' nodes already exist.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the prefix count at node 'a' after inserting "ape"?

A 3

B 2

C 1

D 0

💡 Hint

Check the 'Prefix Count Updated' column at step 3 for node 'a'.

At which step does the prefix count at the second 'p' node become 2?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the variable_tracker row for 'Node p count (second p)' after each step.

If we query prefix "appl", what would be the count returned based on the execution_table?

A 3

B 2

C 1

D 0

💡 Hint

Check the count at node 'l' after 'app' in the visual state and prefix counts.

Concept Snapshot

Count Words with Given Prefix using Trie:
- Insert words char by char
- Create nodes if missing
- Increment count at each node for prefix tracking
- Query prefix by traversing 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 in the Trie represents a character and stores how many words pass through it as a prefix. When inserting words like 'apple', 'app', and 'ape', we create nodes for characters if they don't exist and increment counts at each node. For example, after inserting 'apple', the nodes for 'a', 'p', 'p', 'l', 'e' each have count 1. Inserting 'app' increments counts on 'a', 'p', 'p' to 2. Inserting 'ape' increments counts on 'a', 'p', and creates a new 'e' node under 'p'. When querying a prefix like 'ap', we traverse nodes for 'a' and 'p' and return the count stored at 'p', which is 3, meaning 3 words start with 'ap'. If the prefix is not found, like 'bat', we return 0. This method efficiently counts words sharing prefixes by storing counts during insertion.

Practice

1. What does the function countWordsStartingWith(words: string[], prefix: string): number do in the context of counting words with a given prefix?

easy

A. Counts the total number of characters in all words

B. Counts how many words contain the prefix anywhere inside

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

D. Returns the longest word starting with the prefix

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 goal

   Only Counts how many words in the list start with the given prefix matches the goal of counting words starting exactly with the prefix.

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: Look for words starting exactly with prefix, not containing it [OK]

Common Mistakes:

• Confusing 'start with' and 'contain' prefix
• Thinking it returns words instead of count
• Assuming it counts characters, not words

2. Which of the following TypeScript code snippets correctly counts words starting with a prefix pre in an array words?

easy

A. words.filter(word => word.startsWith(pre)).length

B. words.map(word => word.startsWith(pre)).length

C. words.reduce((count, word) => count + word.includes(pre), 0)

D. words.forEach(word => word.startsWith(pre))

Solution

1. Step 1: Identify correct method to filter words

   The filter method returns an array of words starting with the prefix, then length counts them.

2. Step 2: Check other options for correctness

   words.map(word => word.startsWith(pre)).length returns an array of booleans, so length is total words, not count of matches. words.reduce((count, word) => count + word.includes(pre), 0) uses includes incorrectly and sums booleans without conversion. words.forEach(word => word.startsWith(pre)) does not return a count.

3. Final Answer:

   words.filter(word => word.startsWith(pre)).length -> Option A

4. Quick Check:

   Filter + length counts matches = words.filter(word => word.startsWith(pre)).length [OK]

Hint: Use filter with startsWith, then get length [OK]

Common Mistakes:

• Using map instead of filter for counting
• Using includes instead of startsWith
• Using forEach without counting

3. What is the output of the following TypeScript code?

const words = ['apple', 'app', 'application', 'banana', 'apply'];
const prefix = 'app';
const count = words.filter(word => word.startsWith(prefix)).length;
console.log(count);

medium

A. 3

B. 4

C. 5

D. 2

Solution

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

   Words starting with 'app' are 'apple', 'app', 'application', and 'apply' (4 words).

2. Step 2: Count these words

   Counting them gives 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Words starting with 'app' = 4 [OK]

Hint: Count words starting exactly with prefix 'app' [OK]

Common Mistakes:

• Counting 'banana' mistakenly
• Counting only exact 'app' word
• Confusing includes with startsWith

4. The following TypeScript code is intended to count words starting with prefix pre, but it returns 0. What is the error?

const words = ['prefix', 'preach', 'prevent', 'post'];
const pre = 'pre';
let count = 0;
for (let i = 0; i < words.length; i++) {
  if (words[i].startWith(pre)) {
    count++;
  }
}
console.log(count);

medium

A. Method name should be startsWith, not startWith

B. Variable pre is not defined

C. Loop should start from 1, not 0

D. count should be initialized to 1

Solution

1. Step 1: Check method name correctness

   The method to check prefix is startsWith, but code uses startWith, which is undefined.

2. Step 2: Understand effect of typo

   Because of the typo, condition is always false, so count remains 0.

3. Final Answer:

   Method name should be startsWith, not startWith -> Option A

4. Quick Check:

   Correct method name fixes count [OK]

Hint: Check method spelling: startsWith, not startWith [OK]

Common Mistakes:

• Using startWith instead of startsWith
• Incorrect loop index start
• Wrong count initialization

5. Given a large list of words, which data structure would optimize counting how many words start with a given prefix efficiently for multiple queries?

hard

A. Array sorted alphabetically

B. Stack storing words

C. Hash Map with full words as keys

D. Trie (Prefix Tree)

Solution

1. Step 1: Understand prefix query optimization

   Trie stores words by characters in a tree, allowing fast prefix searches.

2. Step 2: Compare other data structures

   Sorted arrays require binary search but less efficient for many prefix queries. Hash maps store full words, not prefixes. Stacks do not support prefix queries efficiently.

3. Final Answer:

   Trie (Prefix Tree) -> Option D

4. Quick Check:

   Trie enables fast prefix counts [OK]

Hint: Use Trie for fast prefix counting in many queries [OK]

Common Mistakes:

• Choosing array or hash map for prefix queries
• Not knowing Trie supports prefix efficiently
• Confusing stack usage for prefix search