Count Words with Given Prefix in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the problem 'Count Words with Given Prefix' ask you to do?

It asks you to find how many words in a list start with a specific prefix.

intermediate

Why is a Trie (prefix tree) useful for counting words with a given prefix?

A Trie stores words so that common prefixes share nodes, making it fast to count how many words start with a prefix by traversing the prefix path.

beginner

In simple terms, how do you count words with a prefix using a loop?

Check each word one by one and count it if it starts with the prefix.

beginner

What TypeScript string method helps check if a word starts with a prefix?

The method is startsWith(), which returns true if the string begins with the given prefix.

intermediate

What is the time complexity of counting words with a prefix by checking each word individually?

It is O(n * m), where n is the number of words and m is the length of the prefix, because each word is checked against the prefix.

Which TypeScript method checks if a string starts with a specific prefix?

A startsWith()

B includes()

C endsWith()

D substring()

The startsWith() method returns true if the string begins with the given prefix.

What data structure is best for efficiently counting words with a common prefix?

A Trie

B Stack

C Queue

D Linked List

A Trie stores words by their prefixes, allowing fast prefix counting.

If you have 1000 words and a prefix of length 3, what is the rough time complexity to count words with that prefix by checking each word?

A O(1000)

B O(3)

C O(1000 * 3)

D O(1)

You check each of the 1000 words against the prefix of length 3, so O(n * m).

What will the output be after counting words with prefix 'app' in ['apple', 'app', 'banana', 'application']?

A 1

B 3

C 2

D 4

'apple', 'app', and 'application' all start with 'app', so count is 3.

Which of these is NOT a good way to count words with a prefix?

A Using a Trie

B Checking each word with startsWith()

C Sorting words and binary searching prefix

D Using a stack to store words

A stack does not help with prefix counting.

Explain how you would count the number of words starting with a given prefix using a simple loop.

Think about checking each word one by one.

Describe why a Trie is efficient for counting words with a given prefix compared to checking each word individually.

Imagine a tree where common beginnings are stored once.