2255. Count Prefixes of a Given String


Problem Description

You are provided with an array words containing a list of strings, and a single string s. Both the strings in words and the string s are made up exclusively of lowercase English letters. Your task is to find out how many of the provided strings in the words array are actually prefixes of the string s.

In the context of this problem, a prefix is defined as a substring that appears right at the beginning of another string. For example, "pre" is a prefix of "prefix". A substring is simply a sequence of characters that are found together in order, within a larger string.

The goal is to return a count of how many strings in words match the beginning of s exactly, character by character, from the first character onward.

Intuition

The intuition behind the solution is straightforward: You need to check every string in the words array and see if that string is a starting substring—or a prefix—of the given string s.

To arrive at the solution, you traverse through each word in the words array and use the function startswith to check if s begins with that word. The startswith function is handy as it does the job of comparing the characters of the potential prefix with the initial characters of the string s.

For each word in the words array, if s starts with that word, you consider it a match and include it in your count of prefix strings. By summing up the boolean values (True is treated as 1, and False is treated as 0 in Python) returned from startswith for each word, you get the total number of strings in the words array that are a prefix of s.

The solution is elegant because it utilizes the capabilities of Python's list comprehensions and startswith method to perform the task in a concise way, avoiding manual iteration and condition checks.

Solution Approach

The solution involves a very simple yet effective approach. It doesn't require complicated algorithms or data structures. Here, Python's built-in string method and list comprehension are used to achieve the goal in an efficient manner. The steps below break down the solution:

  1. Utilizing startswith: The method startswith is used on the string s to check if it starts with a certain substring. This method returns True if s starts with the given substring, and False otherwise.

  2. List Comprehension for Iteration and Condition Check: Instead of writing a loop to iterate over each word in words, list comprehension is used, which is a concise way to create lists based on existing lists. In this case, it's used to create a list of boolean values, where each boolean indicates whether the corresponding word in words is a prefix of s.

  3. Summation of Boolean Values: In Python, the Boolean True has an integer value of 1, and False has an integer value of 0. Thus, by summing up the list created by list comprehension, it counts the number of True values, which represents the number of words that are prefixes of s.

Here's how the implementation looks:

1class Solution:
2    def countPrefixes(self, words: List[str], s: str) -> int:
3        return sum(s.startswith(w) for w in words)

In the above implementation:

  • words: List[str] is the input list of words to check.
  • s: str is the string to compare against.
  • The countPrefixes method returns an integer int which is the count of prefixes.
  • The expression s.startswith(w) for w in words generates a generator having True or False for each word in words.
  • The sum(...) function takes the generator and adds up all True values resulting in the count of words that are a prefix to s.

Despite the simplicity of this solution, it is very effective for this problem. No additional space is needed beyond the input, and each word is checked exactly once, resulting in a time complexity that is linear to the number of words times the average length of the words.

Example Walkthrough

Let's say we are given the following array of words and the string s:

1words = ["a", "app", "appl"]
2s = "apple"

We want to find out how many of these words are prefixes of the string s.

  • The string s is "apple".
  • The first word in our array is "a", which is indeed the first letter of "apple". So, "a" is a prefix of "apple".
  • The second word is "app", which matches the first three letters of "apple". Therefore, "app" is also a prefix of "apple".
  • The third word is "appl", which matches the first four letters of "apple". "appl" is a prefix as well.

The process for the solution is as follows:

  1. Utilizing startswith: We use startswith to check if "apple" (s) starts with "a" (words[0]). It returns True.
  2. We repeat this for "app" (words[1]) and "apple" starts with "app" as well, so it returns True.
  3. Finally, we check "appl" (words[2]) and find that "apple" does start with "appl", hence it returns True.

Now, let's construct the list comprehension by evaluating s.startswith(w) for each w in words:

1matches = [s.startswith(w) for w in words]

This list comprehension would result in:

1matches = [True, True, True]
  1. Summation of Boolean Values: We then sum up these boolean values:
1count = sum(matches)

count would therefore be 3 since we have three True values.

In the actual implementation using the provided solution approach, it would look like this:

1class Solution:
2    def countPrefixes(self, words: List[str], s: str) -> int:
3        return sum(s.startswith(w) for w in words)

When calling the countPrefixes method with our words and s:

1solution = Solution()
2result = solution.countPrefixes(words, "apple")

result would be equal to 3, indicating that there are three prefixes of "apple" in the given list of words. This example illustrates the efficacy and simplicity of the solution when applied to a small set of data.

Python Solution

1from typing import List
2
3class Solution:
4    # Function to count the number of words that are prefixes of a given string
5    def count_prefixes(self, words: List[str], s: str) -> int:
6        # Initialize the count to 0
7        count = 0
8
9        # Iterate over each word in the list
10        for word in words:
11            # Check if the current word is a prefix of the string s
12            if s.startswith(word):
13                # If it is a prefix, increment the count
14                count += 1
15
16        # After the loop, return the total count
17        return count
18
19# Example of how to use the class:
20# solution = Solution()
21# result = solution.count_prefixes(["a", "b", "c", "a"], "ac")
22# print(result)  # Should print the number of prefixes found in the string "ac"
23

Java Solution

1class Solution {
2    // Method to count how many strings in the array are prefixes of the given string
3    public int countPrefixes(String[] words, String s) {
4        int count = 0;  // Initialize a counter to keep track of prefix matches
5      
6        // Iterate through each word in the array
7        for (String word : words) {
8            // Check if the string 's' starts with the current word
9            if (s.startsWith(word)) {
10                count++;  // If it does, increment the counter
11            }
12        }
13      
14        // Return the final count of prefix matches
15        return count;
16    }
17}
18

C++ Solution

1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    // Function to count the number of words in 'words' that are prefixes of the string 's'.
8    // Params:
9    // words - vector of strings that we will check against the string 's'
10    // s - the string against which we are checking the prefixes
11    // Returns the count of prefixes from 'words' that are found at the start of string 's'.
12    int countPrefixes(vector<string>& words, string s) {
13        int count = 0; // Initialize a counter to keep track of the prefixes
14        // Iterate through each word in the vector 'words'
15        for (const string& word : words) {
16            // Increase the count if the string 's' starts with the current word
17            // Note: starts_with is a standard C++20 string method
18            count += s.starts_with(word);
19        }
20        // Return the final count of prefix occurrences
21        return count;
22    }
23};
24

Typescript Solution

1/**
2 * Counts the number of strings in a given array that are prefixes of a particular string.
3 * 
4 * @param {string[]} words - An array of words to check for prefix status.
5 * @param {string} targetString - The string to check prefixes against.
6 * @return {number} - The count of words that are prefixes of the target string.
7 */
8function countPrefixes(words: string[], targetString: string): number {
9    // Filter the array of words, keeping only those that are prefixes of targetString
10    const prefixWords = words.filter(word => targetString.startsWith(word));
11  
12    // Return the length of the filtered array, which represents the number of prefixes
13    return prefixWords.length;
14}
15

Time and Space Complexity

The time complexity of the given code is O(m * n), where m is the number of words in the list words and n is the length of the string s. This is because for each word in words, the startswith method checks if the string s starts with that word, and this check can take up to O(n) time in the worst case for each word.

The space complexity of the code is O(1) as it does not allocate any additional space that is dependent on the size of the input—the only extra space used is for the sum operation, which is a constant space usage not affected by the input size.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫