Skip to content

2255. Count Prefixes of a Given String

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.

Solutions

Solution 1: Traversal Counting

We directly traverse the array words, and for each string w, we check if s starts with w as a prefix. If it does, we increment the answer by one.

After the traversal, we return the answer.

The time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the lengths of the array words and the string s, respectively. The space complexity is \(O(1)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int countPrefixes(String[] words, String s) {
        int ans = 0;
        for (String w : words) {
            if (s.startsWith(w)) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int ans = 0;
        for (auto& w : words) {
            ans += s.starts_with(w);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func countPrefixes(words []string, s string) (ans int) {
    for _, w := range words {
        if strings.HasPrefix(s, w) {
            ans++
        }
    }
    return
}

1
2
3
function countPrefixes(words: string[], s: string): number {
    return words.filter(w => s.startsWith(w)).length;
}

Comments