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

Recall & Review

beginner

What does 'Count Words with Given Prefix' mean in simple terms?

It means finding how many words in a list start with a certain set of letters (prefix). For example, counting words starting with "pre" in ["prefix", "prevent", "apple"] gives 2.

intermediate

Which data structure is commonly used to efficiently count words with a given prefix?

A Trie (prefix tree) is commonly used because it stores words by their letters and allows quick counting of words sharing the same prefix.

intermediate

How does a Trie help in counting words with a given prefix?

Each node in a Trie can keep track of how many words pass through it. To count words with a prefix, we follow the prefix letters down the Trie and read the count stored at the last node.

intermediate

What is the time complexity to count words with a prefix using a Trie?

It is O(k), where k is the length of the prefix, because we only follow the prefix letters down the Trie without scanning all words.

beginner

What is a simple approach to count words with a prefix without using a Trie?

You can check each word in the list and see if it starts with the prefix. This takes O(n * k) time, where n is number of words and k is prefix length.

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

A Trie

B Stack

C Queue

D Linked List

Trie stores words by prefixes and allows quick counting of words sharing the same prefix.

What is the time complexity to count words with prefix length k using a Trie?

A O(n)

B O(n*k)

C O(1)

D O(k)

Counting words with a prefix in a Trie takes O(k) time, where k is the prefix length.

If you have 1000 words and prefix length 3, what is the time complexity of brute force counting?

A O(3000)

B O(3)

C O(1000)

D O(1)

Brute force checks each word's first 3 letters, so O(n*k) = O(1000*3) = O(3000).

What does each node in a Trie typically store to help count words with a prefix?

A The last letter only

B The entire word

C Number of words passing through the node

D The word length

Each node stores how many words pass through it to quickly count words with that prefix.

Which of these is NOT a benefit of using a Trie for prefix counting?

A Fast prefix search

B Easy to implement

C Supports prefix counting in O(k)

D Memory efficient for large alphabets

Tries can be complex to implement compared to simple loops.

Explain how a Trie data structure helps count words with a given prefix.

Think about how words share common beginnings.

Describe the difference between brute force and Trie-based methods for counting words with a prefix.

Compare speed and memory use.