Counting Words With A Given Prefix - Leetcode Solution

Problem Statement:

Given a string s and a prefix prefix, count the number of words in s that have the prefix prefix as a prefix.

A word is defined as a contiguous sequence of non-space characters.

Constraints:

1 <= s.length <= 2000 1 <= prefix.length <= 2000 s and prefix consist of lowercase English letters and spaces.

Example 1:

Input: s = "hello world", prefix = "he" Output: 1 Explanation: There is only one word that starts with the prefix "he" - "hello".

Example 2:

Input: s = "love love love", prefix = "lo" Output: 3 Explanation: All three words in the string start with the prefix "lo" - "love".

Solution:

The approach to solve the Counting Words With A Given Prefix problem is relatively straightforward. We can simply split the string into words using the split() function and count the number of words that start with the prefix prefix.

Algorithm:

1. Initialize a counter variable, say count, to 0.
2. Split the string s into words using the split() function. Store the resulting list in a variable called words.
3. Loop through each word in the words list and:
4. Check if the first len(prefix) characters of the word match the prefix. If they do, increment the count variable.
5. Return the final value of count.

Python Code:

def count_words_with_prefix(s: str, prefix: str) -> int: count = 0 words = s.split() for word in words: if word.startswith(prefix): count += 1 return count

Complexity Analysis:

The time complexity of the count_words_with_prefix() function is O(n), where n is the number of words in the string s.

The space complexity of the function is O(n), where n is the number of words in the string s, as we are storing the list of words in memory.

1