Count Prefixes of a Given String
EasyPrompt
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 <= 10001 <= words[i].length, s.length <= 10words[i]andsconsist of lowercase English letters only.
Approaches
2 approaches with complexity analysis and trade-offs.
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
-
- Initialize an integer variable
countto 0.
- Initialize an integer variable
-
- Iterate through each
stringin thewordsarray.
- Iterate through each
-
- For each
string, check ifsstarts with it using the built-ins.startsWith(string)method.
- For each
-
- If the check returns
true, it means the current string is a prefix ofs, so incrementcount.
- If the check returns
-
- After the loop finishes, return the final
count.
- After the loop finishes, return the final
Walkthrough
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
Time
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
O(1), as we only use a single integer variable for the counter, requiring constant extra space.
Trade-offs
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
sfor each word, which involves redundant comparisons if many words share common prefixes.
Solutions
Solution
public class Solution { public int CountPrefixes(string[] words, string s) { return words.Count(w => s.StartsWith(w)); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.