💬 Discord
Sign In
NeetCode #478LC-2185EasyTries
← Back to All Problems

#478 · #2185 · Counting Words With a Given Prefix(统计包含给定前缀的字符串)

📌 Problem Statement & Constraints

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. Constraints: 1 <= words.length <= 100, 1 <= words[i].length, pref.length <= 100.

💡 Core Algorithmic Approaches

  1. A direct count with startswith is the whole solution.
  2. Building a trie would be over-engineering at these constraints, though it is the scalable approach.
  3. The count is a simple generator sum.
  4. Note that pref may be longer than some words, in which case startswith correctly returns False.

💻 Benchmark Python3 Implementation

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        return sum(1 for w in words if w.startswith(pref))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * L): each word is compared against the prefix.
💾 Space Complexity
O(1) beyond the input.

⚠️ Interview Pitfalls & Follow-ups

  • Using pref in w: that tests a substring, not a prefix.
  • Assuming pref is shorter than every word: it may be longer.
  • Building a trie: unnecessary at these constraints, though it would be the answer for a large streaming input.