Problem

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.

Examples

Example 1:

1
2
3

Input: words = ["pay","**_at_** tention","practice","_**at**_ tend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "_**at**_ tention" and "_**at**_ tend".

Example 2:

1
2
3

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.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Using Starts with

Here is the approach:

  • Create a counter ans initialized to 0.
  • Iterate through each string word in words.
  • For each word, check if it starts with pref using the startsWith method in Java and the startswith method in Python.
  • If it does, increment the counter ans.
  • Return the counter ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class Solution {
    public int prefixCount(String[] words, String pref) {
        int ans = 0;
        for (String word : words) {
            if (word.startsWith(pref)) {
                ans++;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        ans: int = 0
        for word in words:
            if word.startswith(pref):
                ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O(n * l), where n is the number of words in the array, and l is the length of the longest word. This is because for each of the n words, we may need to check up to m characters to verify if the word starts with the given prefix.
  • 🧺 Space complexity: O(1) as we are using some variables here and there