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

🟢   🔖  数组 字符串  🔗 力扣 LeetCode

题目

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.

题目大意

给你一个字符串数组 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. 初始化计数器：count 用于统计满足条件的单词数量。
2. 遍历单词：使用 for...of 遍历 words 中的每个单词。
3. 检查前缀：使用 startsWith 方法判断s是否以单词开头。
4. 更新计数器：如果满足条件，计数器 count 增加。
5. 返回结果：最后返回满足条件的单词数量。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是 words 的长度，n 是单词的平均长度，对于每个单词，startsWith 方法需要检查前缀的长度为单词长度。
• 空间复杂度：O(1)，只使用了一个计数器变量，没有额外的存储需求。

代码

/**
 * @param {string[]} words
 * @param {string} s
 * @return {number}
 */
var countPrefixes = function (words, s) {
	let count = 0; // 初始化计数器
	for (let word of words) {
		// 遍历每个单词
		if (s.startsWith(word)) {
			// 检查是否以 word 为前缀
			count++; // 如果满足条件，计数器 +1
		}
	}
	return count; // 返回最终计数结果
};

相关题目

题号	标题	题解	标签	难度	力扣
1455	检查单词是否为句中其他单词的前缀	[✓]	双指针 字符串 字符串匹配	🟢	🀄️ 🔗
1961	检查字符串是否为数组前缀	[✓]	数组 双指针 字符串	🟢	🀄️ 🔗
2185	统计包含给定前缀的字符串	[✓]	数组 字符串 字符串匹配	🟢	🀄️ 🔗