Count Prefixes of a Given String

EASY

Description

You are given a string array words and a string s, where words[i] and s comprise only of lowercase English letters.

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

A prefix of a string is a substring that occurs at the beginning of the string. A substring is a contiguous sequence of characters within a string.

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 = "abc" are:
"a", "ab", and "abc".
Thus the number of strings in words which are a prefix of s is 3.

Example 2:

Input: words = ["a","a"], s = "aa"
Output: 2
Explanation:
Both of the strings are a prefix of s. 
Note that the same string can occur multiple times in words, and it should be counted each time.

Constraints:

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

Approaches

Checkout 2 different approaches to solve Count Prefixes of a Given String. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

This approach iterates through each word in the input array words and checks if it is a prefix of the string s. A simple counter is used to keep track of the number of words that satisfy this condition.

Algorithm

1. Initialize an integer variable count to 0.
1. Iterate through each string in the words array.
1. For each string, check if s starts with it using the built-in s.startsWith(string) method.
1. If the check returns true, it means the current string is a prefix of s, so increment count.
1. After the loop finishes, return the final count.

We initialize a counter variable, prefixCount, to zero. We then loop through every word in the words array. For each word, we can use the built-in startsWith() method of the String class to check if s begins with that word. The s.startsWith(word) method efficiently compares the characters of word with the beginning characters of s. If s.startsWith(word) returns true, it means word is a prefix of s, and we increment prefixCount. After checking all the words in the array, the final value of prefixCount is the answer. This method is straightforward to implement and understand, and given the problem's constraints, it is perfectly acceptable.

class Solution {
    public int countPrefixes(String[] words, String s) {
        int count = 0;
        for (String word : words) {
            if (s.startsWith(word)) {
                count++;
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N * L), where `N` is the number of words in the `words` array and `L` is the maximum length of a word. For each of the `N` words, the `startsWith` check takes up to `O(L)` time.Space Complexity: O(1), as we only use a single integer variable for the counter, requiring constant extra space.

Pros and Cons

Pros:

Very simple to understand and implement.
Highly efficient in terms of space complexity.
For the given constraints, it's fast enough and might even outperform more complex solutions due to lower overhead.

Cons:

Can be inefficient if the number of words (N) or the length of the words (L) is very large.
It repeatedly scans the beginning of string s for each word, which involves redundant comparisons if many words share common prefixes.

Code Solutions

Checking out 4 solutions in different languages for Count Prefixes of a Given String. Click on different languages to view the code.

public class Solution {
    public int CountPrefixes(string[] words, string s) {
        return words.Count(w => s.StartsWith(w));
    }
}

Video Solution

Watch the video walkthrough for Count Prefixes of a Given String

Data Structures:

ArrayString