{x}
blog image

Counting Words With a Given Prefix

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

 

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

 

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length, pref.length <= 100
  • words[i] and pref consist of lowercase English letters.

Solution Explanation:

The problem asks to count the number of strings in a given array that start with a specific prefix. There are two main approaches to solving this: a straightforward iterative approach and a Trie-based approach.

Approach 1: Iterative Approach

This approach directly iterates through the array of strings and checks if each string starts with the given prefix using the startsWith() method (or equivalent in other languages). This is the most efficient approach for this problem due to its simplicity and linear time complexity.

Time Complexity: O(N*M), where N is the number of words and M is the length of the prefix. In the worst case, we might need to compare the prefix with the beginning of every word.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Examples:

The code examples provided in various languages implement this approach efficiently:

  • Python: uses a generator expression with sum() for conciseness.
  • Java: uses a simple for loop and startsWith().
  • C++: uses a range-based for loop and find() (which returns 0 if the prefix is at the beginning).
  • Go: uses a for loop and strings.HasPrefix().
  • TypeScript: uses reduce() for a concise solution.
  • Rust: uses iterators and starts_with() for a concise and efficient solution.
  • C: uses a for loop and strncmp() for character-by-character comparison up to the prefix length.

Approach 2: Trie-based Approach

This approach uses a Trie data structure to store the words. A Trie is a tree-like data structure that is very efficient for prefix-based searches. We insert all words into the Trie, then search for the count of words with the given prefix. While this approach is more complex to implement, it could be more efficient for scenarios with many words and repeated prefixes. However, for the given constraints (1 <= words.length <= 100), the iterative approach is likely more efficient due to lower constant overhead.

Time Complexity: O(NL + ML), where N is the number of words, L is the average length of words, and M is the length of the prefix. The insertion into the Trie takes O(NL) and searching takes O(ML).

Space Complexity: O(N*L) in the worst-case scenario, where we store all the characters of all words in the Trie.

Code Examples:

The Trie-based code examples are more complex, involving Trie node creation and insertion/search methods:

  • All languages implement a Trie class with methods to insert words and search for prefixes. The main function then uses this Trie to count words with the given prefix. The implementation details might differ slightly across languages due to syntax and data structure features but follow the core Trie logic.

Conclusion:

For the problem's constraints, the iterative approach (Approach 1) is generally preferred due to its simplicity and comparable or better performance in this specific context. The Trie-based approach (Approach 2) is more suitable when dealing with a significantly larger number of words or repeated prefixes and when many prefix queries are needed. The iterative approach offers a good balance of readability and efficiency for this problem.