Count Words with Given Prefix in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of countWordsStartingWith after insertions

What is the output of the following TypeScript code that inserts words and counts how many start with a given prefix?

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
      node.count++;
    }
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
trie.insert("apt");
trie.insert("bat");

console.log(trie.countWordsStartingWith("app"));

A 4

B 2

C 3

D 1

💡 Hint

Count how many inserted words start with 'app'.

The words starting with 'app' are 'apple', 'app', and 'application', so the count is 3.

❓ Predict Output

intermediate

Result of countWordsStartingWith for a prefix not present

What will be the output of the code when counting words starting with prefix 'cat' after inserting some words?

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
      node.count++;
    }
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

const trie = new Trie();
trie.insert("dog");
trie.insert("deer");
trie.insert("deal");

console.log(trie.countWordsStartingWith("cat"));

A 0

B 1

C 3

D 2

💡 Hint

Check if any inserted word starts with 'cat'.

No inserted word starts with 'cat', so the count is 0.

🔧 Debug

advanced

Identify the bug in countWordsStartingWith method

The following TypeScript code is supposed to count how many words start with a given prefix. However, it returns incorrect results. What is the bug?

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.count++;
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

A The insert method does not create new nodes for characters.

B The count is incremented only at the end node, so intermediate nodes have count 0, causing wrong prefix counts.

C The countWordsStartingWith method does not check if prefix exists.

D The root node's count is incremented incorrectly.

💡 Hint

Think about when counts are updated during insertion.

The count should be incremented at every node along the path during insertion to reflect how many words pass through that node. Here, count is incremented only at the last node, so prefix counts are wrong.

❓ Predict Output

advanced

Output after multiple insertions and prefix counts

Given the following code, what is the output of the two console.log statements?

DSA Typescript

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

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
      node.count++;
    }
  }

  countWordsStartingWith(prefix: string): number {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        return 0;
      }
      node = node.children.get(ch)!;
    }
    return node.count;
  }
}

const trie = new Trie();
trie.insert("car");
trie.insert("card");
trie.insert("care");
trie.insert("cart");
trie.insert("cat");

console.log(trie.countWordsStartingWith("car"));
console.log(trie.countWordsStartingWith("ca"));

A

4
5

B

4
4

C

3
5

D

3
4

💡 Hint

Count words starting with 'car' and 'ca'.

'car', 'card', 'care', and 'cart' start with 'car' (4 words). All five words start with 'ca'.

🧠 Conceptual

expert

Why use a Trie for counting words with a prefix?

Which of the following is the main advantage of using a Trie data structure to count how many words start with a given prefix compared to scanning all words in a list?

A Trie automatically removes duplicate words.

B Trie stores words in sorted order, so counting is faster.

C Trie uses less memory than storing words in a list.

D Trie allows prefix counts in time proportional to prefix length, not total words.

💡 Hint

Think about how prefix queries scale with number of words.

Trie lets you find prefix counts by following nodes for each prefix character, so time depends on prefix length only, not total words. Scanning a list checks every word, which is slower.

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