Optimized Set-Based Solution | O(n + m) Time | Python 3
IntuitionWe need to count how many words in words are prefixes of the string s. A prefix is any substring that starts from the beginning of s. Instead of checki
# Intuition
We need to count how many words in words are prefixes of the string s. A prefix is any substring that starts from the beginning of s. Instead of checking each word against s directly (which would be inefficient), we can precompute all valid prefixes of s and store them in a set for quick lookup.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
1. Generate all prefixes of s:
    * A prefix of s is any substring s[:i], where i ranges from 1 to len(s).
    * We store these prefixes in a set to allow quick O(1) lookup.
2. Count the words that exist in the prefix set:
    * For each word in words, check if it exists in the prefix_set.
    * Use a simple sum() function to count the number of matches.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(n+m)
    * Generating prefixes: O(n) (since we extract s[:i] substrings and insert them into a set).
    * Checking membership for each word: O(m) (since each lookup in a set is O(1) on average).
    * Total Complexity: O(n+m).
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(n)
    * Prefix set storage: O(n) (storing at most n substrings).
    * No extra space apart from input storage.
    * Total Complexity: O(n).
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        prefix_set = {s[:i] for i in range(1, len(s) + 1)}  
        return sum(1 for word in words if word in prefix_set)

```


![sad-thumbs-up-cat.3.meme.webp](https://assets.leetcode.com/users/images/312ad46a-0b11-4679-aa96-f4bed0d8acef_1743708178.2284577.webp)
['Array', 'String', 'Python3']