Easy

题目描述

给定一个字符串数组 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 仅由小写英文字母组成

解题思路

这是一道简单的字符串匹配题，核心是判断每个单词是否为目标字符串的前缀。

解题思路：

  1. 遍历 words 数组中的每个字符串
  2. 对于每个字符串，检查它是否为 s 的前缀
  3. 判断前缀的方法有多种：
    • 使用内置的 startsWith 方法（推荐）
    • 截取 s 的前 n 位与当前单词比较
    • 逐字符比较

优化考虑： 由于题目约束条件较小（字符串长度不超过10，数组长度不超过1000），直接使用简单的字符串匹配即可，无需复杂的字符串算法如KMP。

时间复杂度主要取决于字符串比较的开销，对于每个单词，最坏情况下需要比较其完整长度。

推荐解法： 使用语言内置的前缀判断函数，代码简洁且效率高。

代码实现

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int count = 0;
        for (const string& word : words) {
            if (s.substr(0, word.length()) == word) {
                count++;
            }
        }
        return count;
    }
};

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

public class Solution {
    public int CountPrefixes(string[] words, string s) {
        int count = 0;
        foreach (string word in words) {
            if (s.StartsWith(word)) {
                count++;
            }
        }
        return count;
    }
}

var countPrefixes = function(words, s) {
    let count = 0;
    for (const word of words) {
        if (s.startsWith(word)) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n × m)n 是 words 数组长度，m 是平均字符串长度
空间复杂度O(1)只使用常数额外空间

相关题目