Jobs

Interviews

Discussions

Counting Words With a Given Prefix #780 Most Asked

Easy

Microsoft

1 view

Topics:

ArraysStrings

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Try coding it in LeetCode

Counting Words With a Given Prefix #780 Most Asked

Easy

Microsoft

1 view

Topics:

ArraysStrings

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array of words and the prefix string be empty or null?
Are the words in the array and the prefix case-sensitive?
What is the maximum length of the words in the array and the prefix string?
Should I return the count of words that *start with* the prefix, or just *contain* the prefix?
If no words in the array have the given prefix, what should I return?

Brute Force Solution

Approach

The brute force way to solve this is to look at each word in the list one by one. For each word, we need to see if the prefix matches the beginning of that word.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the given prefix is the beginning part of the current word.
If the prefix matches the beginning of the current word, add one to our count.
If it does not match, don't change the count.
Move on to the next word in the list and repeat the process (check for the prefix, and increase the count if needed).
Keep doing this until we have checked every word in the list.
The final count is the total number of words that start with the given prefix.

Code Implementation

def count_words_with_prefix_brute_force(list_of_words, prefix): 
    word_count_with_matching_prefix = 0

    for word in list_of_words:
        # Check if the prefix matches the start of the word
        if word.startswith(prefix): 

            # Increment the counter because it starts with the prefix
            word_count_with_matching_prefix += 1

    return word_count_with_matching_prefix

Big(O) Analysis

Time Complexity

O(n*m) – We iterate through each of the n words in the input list. For each word, we compare it with the prefix which has length m. The comparison itself takes O(m) time in the worst case (when the prefix almost matches the word). Therefore, the total time complexity is O(n*m), where n is the number of words and m is the length of the prefix. This assumes string comparison is not a constant time operation and depends on the length of the prefix being checked.

Space Complexity

O(1) – The provided algorithm iterates through the input list of words and checks each word individually. It only utilizes a counter variable to keep track of the number of words with the given prefix. No auxiliary data structures like lists or hashmaps are created, and no recursive calls are made. Therefore, the space required remains constant regardless of the number of words (N) in the input list, resulting in O(1) space complexity.

Optimal Solution

Approach

To efficiently count words starting with a given prefix, we avoid checking every word individually. We compare the prefix with the beginning of each word and increment the count only when a match is found.

Here's how the algorithm would work step-by-step:

Take the given prefix and the list of words as input.
Go through each word in the list one by one.
For each word, see if the prefix is at the beginning of the word.
If the prefix matches the start of the word, increase the count.
After checking all the words, return the total count of words that started with the given prefix.

Code Implementation

def count_words_with_prefix(list_of_words, search_prefix):
    prefix_count = 0

    # Iterate through each word in the input list.
    for word in list_of_words:

        # Check if the prefix matches the beginning of the word.
        if word.startswith(search_prefix):

            prefix_count += 1

    # Return the total count of words with the given prefix.
    return prefix_count

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the n words in the input list. For each word, it compares the given prefix of length m to the beginning of the word. In the worst-case scenario, the comparison of the prefix to the word takes m operations. Therefore, the total time complexity is proportional to n * m, where n is the number of words and m is the length of the prefix.

Space Complexity

O(1) – The algorithm iterates through the list of words and checks each word against the given prefix. No auxiliary data structures like arrays, lists, or hash maps are created to store intermediate results or visited words. Only a counter variable to store the number of matching words and potentially a few variables to hold indices or boolean flags during the prefix comparison are needed, which requires constant space regardless of the number of words or the length of the prefix. Therefore, the space complexity is O(1), meaning constant space.

Edge Cases

Case	How to Handle
words is null or empty	Return 0 immediately to avoid NullPointerException or incorrect count.
prefix is null or empty	If prefix is null, throw IllegalArgumentException; if empty, return the length of the words array, as all words have an empty prefix.
words contains null or empty strings	Skip null or empty strings in words to avoid NullPointerException or incorrect prefix check.
prefix is longer than any word in words	No words will have that prefix, so the correct count is 0.
words array contains very long strings	Iterating through long strings could impact performance, so consider optimizing prefix matching with methods like startsWith.
prefix contains special characters or unicode characters	The startsWith() method should handle unicode characters correctly, but test for unexpected behavior with specific special characters.
Large words array	Algorithm's time complexity of O(N*M) where N is the size of the array and M is max length of words should be efficient enough, but consider Trie if performance becomes a concern.
All words in array have the given prefix	The loop should iterate through all words and increment the counter for each, ultimately returning the length of the words array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array of words and the prefix string be empty or null?
Are the words in the array and the prefix case-sensitive?
What is the maximum length of the words in the array and the prefix string?
Should I return the count of words that *start with* the prefix, or just *contain* the prefix?
If no words in the array have the given prefix, what should I return?

Brute Force Solution

Approach

The brute force way to solve this is to look at each word in the list one by one. For each word, we need to see if the prefix matches the beginning of that word.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the given prefix is the beginning part of the current word.
If the prefix matches the beginning of the current word, add one to our count.
If it does not match, don't change the count.
Move on to the next word in the list and repeat the process (check for the prefix, and increase the count if needed).
Keep doing this until we have checked every word in the list.
The final count is the total number of words that start with the given prefix.

Code Implementation

def count_words_with_prefix_brute_force(list_of_words, prefix): 
    word_count_with_matching_prefix = 0

    for word in list_of_words:
        # Check if the prefix matches the start of the word
        if word.startswith(prefix): 

            # Increment the counter because it starts with the prefix
            word_count_with_matching_prefix += 1

    return word_count_with_matching_prefix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the given prefix and the list of words as input.
Go through each word in the list one by one.
For each word, see if the prefix is at the beginning of the word.
If the prefix matches the start of the word, increase the count.
After checking all the words, return the total count of words that started with the given prefix.

Code Implementation

def count_words_with_prefix(list_of_words, search_prefix):
    prefix_count = 0

    # Iterate through each word in the input list.
    for word in list_of_words:

        # Check if the prefix matches the beginning of the word.
        if word.startswith(search_prefix):

            prefix_count += 1

    # Return the total count of words with the given prefix.
    return prefix_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
words is null or empty	Return 0 immediately to avoid NullPointerException or incorrect count.
prefix is null or empty	If prefix is null, throw IllegalArgumentException; if empty, return the length of the words array, as all words have an empty prefix.
words contains null or empty strings	Skip null or empty strings in words to avoid NullPointerException or incorrect prefix check.
prefix is longer than any word in words	No words will have that prefix, so the correct count is 0.
words array contains very long strings	Iterating through long strings could impact performance, so consider optimizing prefix matching with methods like startsWith.
prefix contains special characters or unicode characters	The startsWith() method should handle unicode characters correctly, but test for unexpected behavior with specific special characters.
Large words array	Algorithm's time complexity of O(N*M) where N is the size of the array and M is max length of words should be efficient enough, but consider Trie if performance becomes a concern.
All words in array have the given prefix	The loop should iterate through all words and increment the counter for each, ultimately returning the length of the words array.

0/0 Microsoft questions completed

0/0 completed