algoadvance

Given a list of strings words and a string s, determine the number of strings in words that are a prefix of s.

A string word is a prefix of s if s starts with word.

Example:

Input: words = ["a","b","c","ab","bc","abc"], s = "abc"
Output: 3
Explanation: The strings in words that are prefixes of s are "a", "ab", and "abc".

Clarifying Questions

1. Can the input string s be empty?
   • It is assumed that s will be a non-empty string as per typical problem constraints.
2. Can the words in the list words be empty or contain empty strings?
   • It’s generally best to consider and handle edge cases. An empty string as a word cannot be a prefix of any non-empty string.
3. What should be the return type?
   • The return type should be an integer representing the count of prefixes.

Strategy

1. Iterate through each word in the list words.
2. Check if the word is a prefix of the string s.
   • Utilize Python’s string method .startswith() which returns True if the given string starts with the specified prefix.
3. Count the number of words that satisfy this condition.

Code

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

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

Time Complexity

• Checking if a word is a prefix: The .startswith() method has a time complexity of O(m) where m is the length of the word.
• Iterating through each word in words: Let n be the number of words in the list.
• Overall complexity: O(n * m) in the worst case where m is the maximum length of any word in words.

Thus, the time complexity is generally efficient given that string comparison operations are fast in Python. This should handle typical constraints comfortably unless words or s are exceptionally large.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?