Easy

题目描述

给你一个字符串数组 words 和一个字符串 pref。

返回 words 中以 pref 作为前缀的字符串的数目。

字符串 s 的前缀是 s 的任一前导连续子字符串。

示例 1：

输入：words = ["pay","attention","practice","attend"], pref = "at"
输出：2
解释：以 "at" 作为前缀的 2 个字符串分别是："attention" 和 "attend"。

示例 2：

输入：words = ["leetcode","win","loops","success"], pref = "code"
输出：0
解释：不存在以 "code" 作为前缀的字符串。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length, pref.length <= 100
  • words[i] 和 pref 仅由小写英文字母组成

解题思路

这道题是一个简单的字符串前缀匹配问题。我们需要统计数组中有多少个字符串以给定前缀开头。

解题思路：

  1. 暴力遍历法（推荐）：遍历每个单词，检查是否以指定前缀开头。可以使用字符串的内置方法来判断前缀。

  2. 字符逐一比较法：对于每个单词，逐字符与前缀进行比较，确保前缀长度不超过单词长度。

具体步骤：

  • 初始化计数器为 0
  • 遍历 words 数组中的每个字符串
  • 对于每个字符串，检查它是否以 pref 开头
  • 如果是前缀，计数器加 1
  • 返回最终计数

时间复杂度优化： 由于题目数据规模较小（最多100个单词，每个单词最长100字符），使用内置字符串方法是最简洁高效的选择。

代码实现

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

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

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

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

复杂度分析

复杂度分析
时间复杂度O(n × m)，其中 n 是 words 的长度，m 是 pref 的长度。对于每个单词都需要进行前缀比较
空间复杂度O(1)，只使用了常数级别的额外空间

相关题目