2255-统计是给定字符串前缀的字符串数目

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。

请你返回 words 中是字符串 s **前缀 **的 字符串数目 。

一个字符串的 前缀 是出现在字符串开头的子字符串。 子字符串 是一个字符串中的连续一段字符序列。

示例 1：

**输入：** words = ["a","b","c","ab","bc","abc"], s = "abc"
**输出：** 3
**解释：**
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。

示例 2：

**输入：** words = ["a","a"], s = "aa"
**输出：** 2
**解释：** 两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i] 和 s 只 包含小写英文字母。

方法一：遍历判断

思路与算法

我们可以遍历 words 数组，并判断每个字符串 word 是否是 s 的前缀。与此同时，我们用 res 来维护包含前缀字符串的数量。如果 word 是 s 的前缀，则我们将 res 加上 1。最终，我们返回 res 作为答案。

关于判断 word 是否为 s 的前缀，某些语言如 Python 有字符串对应的 startswith() 方法。对于没有类似方法的语言，我们也可以手动实现以达到相似的效果。

具体地，我们用函数 isPrefix}(\textit{word}) 来实现这一判断。首先当 s 的长度小于 word 时，word 一定不可能是 s 的前缀，此时返回 false。随后，我们从头开始逐字符判断 word 和 s 的对应字符是否相等。如果某个字符不相等，同样返回 false。如果遍历完成 word 后所有字符均相等，则返回 true。

代码

[sol1-C++]

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int res = 0;   // 符合要求字符串个数
        // 判断 word 是否是 s 的前缀
        auto isPrefix = [&](const string& word) -> bool {
            if (s.size() < word.size()) {
                return false;
            }
            for (int i = 0; i < word.size(); ++i) {
                if (word[i] != s[i]) {
                    return false;
                }
            }
            return true;
        };
        
        for (const string& word: words) {
            if (isPrefix(word)) {
                ++res;
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def countPrefixes(self, words: List[str], s: str) -> int:
        res = 0   # 符合要求字符串个数
        for word in words:
            if s.startswith(word):
                res += 1
        return res

复杂度分析

• 时间复杂度：O(mn)，其中 m 为 words 数组的长度，n 为字符串 s 的长度。每判断 words 中一个字符串的时间复杂度为 O(n)，我们总共需要判断 m 次。

• 空间复杂度：O(1)。