Count Prefixes of a Given String

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

Return the number of strings in words that are a prefix of s.

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

Example 1:

Input: words = ["a","b","c","ab","bc","abc"], s = "abc" Output: 3 Explanation: The strings in words which are a prefix of s = "abc" are: "a", "ab", and "abc". Thus the number of strings in words which are a prefix of s is 3.

Example 2:

Input: words = ["a","a"], s = "aa" Output: 2 Explanation: Both of the strings are a prefix of s. Note that the same string can occur multiple times in words, and it should be counted each time.

def prefix_count(words: list[str], s: str) -> int:
    """Given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

    Return the number of strings in words that are a prefix of s.

    A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.
    For example:
    prefix_count(["a","b","c","ab","bc","abc"], "abc") == 3
    prefix_count(["a","a"], "aa") == 2
    """
    count = 0
    for word in words:
        if s.startswith(word):
            count += 1
    return count


# Naive Solution
# Iterate through the words array.
# For each word, check if the string s starts with that word.
# If it does, increment the count.
# Return the final count.

def prefix_count_naive(words: list[str], s: str) -> int:
    count = 0
    for word in words:
        if s.startswith(word):
            count += 1
    return count


# Optimal Solution
# The optimal solution is the same as the naive solution in this case, because we have to iterate through all words in the worst case
# Time Complexity: O(N * K), where N is the number of words and K is the average length of the words.
# Space Complexity: O(1)

def prefix_count_optimal(words: list[str], s: str) -> int:
    count = 0
    for word in words:
        if s.startswith(word):
            count += 1
    return count


# Big O Time Complexity Analysis
# The time complexity of the solution is O(N * K), where N is the number of words in the words array, and K is the average length of the words.
# This is because we iterate through each word in the words array, and for each word, we check if the string s starts with that word. The startswith() method takes O(K) time in the worst case.


# Big O Space Complexity Analysis
# The space complexity of the solution is O(1), because we only use a constant amount of extra space to store the count.


# Edge Cases
# 1. The words array is empty. In this case, the function should return 0.
# 2. The string s is empty. In this case, the function should return 0 if there are any non-empty strings in words, and the number of empty strings otherwise.
# 3. The words array contains duplicate words. In this case, the function should count each duplicate word as a prefix of s if it is indeed a prefix.
# 4. Some words are longer than s. In this case, those words cannot be prefixes of s, so they shouldn't be counted.
# 5. words and s contain characters other than lowercase English letters. The problem statement specifies that words[i] and s comprise only of lowercase English letters, so this should not occur.


# Example Usage
words = ["a","b","c","ab","bc","abc"]
s = "abc"
print(prefix_count(words, s)) # Output: 3

words = ["a","a"]
s = "aa"
print(prefix_count(words, s)) # Output: 2

words = []
s = "abc"
print(prefix_count(words, s)) # Output: 0

words = [""]
s = "abc"
print(prefix_count(words, s)) # Output: 1

words = ["abc"]
s = ""
print(prefix_count(words, s)) # Output: 0

words = ["", "", ""]
s = ""
print(prefix_count(words, s)) # Output: 3