题目描述
给你一个字符串数组 words
和一个字符串 s
,其中 words[i]
和 s
只包含 小写英文字母。
请你返回 words
中是字符串 s
前缀 的 字符串数目。
一个字符串的 前缀 是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。
样例
输入:words = ["a","b","c","ab","bc","abc"], s = "abc"
输出:3
解释:
words 中是 s = "abc" 前缀的字符串为:
"a","ab" 和 "abc"。
所以 words 中是字符串 s 前缀的字符串数目为 3。
输入:words = ["a","a"], s = "aa"
输出:2
解释:
两个字符串都是 s 的前缀。
注意,相同的字符串可能在 words 中出现多次,它们应该被计数多次。
限制
1 <= words.length <= 1000
1 <= words[i].length, s.length <= 10
words[i]
和s
只 包含小写英文字母。
算法
(枚举) $O(nL)$
- 对于每个给定的字符串,直接判断是否为目标字符串的前缀。
时间复杂度
- 每个字符串需要 $O(L)$ 的时间判断,故总时间复杂度为 $O(nL)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
bool check(const string &w, const string &s) {
if (w.size() > s.size())
return false;
for (int i = 0; i < w.size(); i++)
if (w[i] != s[i])
return false;
return true;
}
public:
int countPrefixes(vector<string>& words, string s) {
int ans = 0;
for (const auto &w : words)
if (check(w, s))
ans++;
return ans;
}
};