algoadvance

You are given an array of strings words and a string pref. A string is considered a suitable word if it starts with the prefix pref.

Return the number of strings in words that are suitable.

Example 1

Input: words = ["pay", "attention", "practice", "attend"], pref = "at"
Output: 2

Example 2

Input: words = ["leetcode", "win", "loops", "success"], pref = "code"
Output: 0

Clarifying Questions

  1. Can the words array be empty?
    • Yes, if the words array is empty, the output should be 0.
  2. Is the prefix guaranteed to be non-empty?
    • Yes, the problem statement implies that pref is non-empty.
  3. Are all characters in words and pref lowercase letters?
    • Yes, it is stated that all strings contain lowercase English letters.
  4. What is the maximum length for words and pref?
    • Constraints generally allow up to reasonable lengths typical for such problems on LeetCode. For our implementation, we assume words can have up to 10^4 elements and each string can be up to 100 characters long.

Strategy

  1. Iterate through the list words.
  2. Check if each word starts with the prefix pref using the startswith method.
  3. Count the number of words that match the condition.

Code

def count_words_with_prefix(words, pref):
    count = 0
    for word in words:
        if word.startswith(pref):
            count += 1
    return count

Time Complexity

The time complexity of this solution is O(n * m), where:

This is because the startswith method internally checks up to len(pref) characters for each word, leading to a complexity of O(m) per word. Looping through all words results in the total time complexity of O(n * m). This is efficient given typical constraints in competitive programming.

Example Execution

Let’s walk through the example in the problem statement:

For words = ["pay", "attention", "practice", "attend"] and pref = "at":

  1. “pay” does not start with “at” (count remains 0).
  2. “attention” starts with “at” (count increases to 1).
  3. “practice” does not start with “at” (count remains 1).
  4. “attend” starts with “at” (count increases to 2).

Therefore, the function returns 2.

The code is designed to handle the general case and efficiently count words with a given prefix.

Try our interview co-pilot at AlgoAdvance.com