Count Prefixes of a Given String

Difficulty: Easy | Acceptance: 74.30% | Paid: No Topics: Array, String

You are given a string array words and a string s.

A string prefix is a string that can be formed by taking the first k characters of s, where k can be any non-negative integer.

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

• Examples
• Constraints
• Built-in String Methods
• Manual Character Comparison

Examples

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 are "a", "ab", and "abc".

Example 2:

Input: words = ["a","a"], s = "aa"
Output: 2
Explanation:
Both strings in words are a prefix of s.

Constraints

- 1 <= words.length <= 1000
- 1 <= words[i].length, s.length <= 10
- words[i] and s consist of lowercase English letters only.

Built-in String Methods

Intuition Most modern programming languages provide built-in methods to check if a string starts with a specific substring. We can iterate through the list of words and use this method to check each word against the target string.

Steps

• Initialize a counter to 0.
• Iterate through each word in the input array.
• For each word, check if the target string starts with the current word.
• If it does, increment the counter.
• Return the counter after processing all words.

from typing import List

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        count = 0
        for w in words:
            if s.startswith(w):
                count += 1
        return count

Complexity

• Time: O(N * L) where N is the number of words and L is the maximum length of a word.
• Space: O(1)
• Notes: This approach is concise and leverages optimized standard library functions.

Manual Character Comparison

Intuition If we want to avoid built-in library functions or understand the underlying mechanics, we can manually compare characters. A word is a prefix of s if the word is shorter than or equal to s and every character in the word matches the corresponding character in s.

Steps

• Initialize a counter to 0.
• Iterate through each word in the input array.
• If the length of the current word is greater than the length of s, skip it (it cannot be a prefix).
• Otherwise, iterate through the characters of the word.
• Compare each character of the word with the character at the same index in s.
• If any character mismatches, break the loop and move to the next word.
• If all characters match, increment the counter.
• Return the counter.

from typing import List

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        count = 0
        for w in words:
            if len(w) > len(s):
                continue
            match = True
            for i in range(len(w)):
                if w[i] != s[i]:
                    match = False
                    break
            if match:
                count += 1
        return count

Complexity

• Time: O(N * L) where N is the number of words and L is the maximum length of a word.
• Space: O(1)
• Notes: This approach is fundamental and works in any programming environment without relying on specific library methods.