1684.md

title	description	keywords
1684. 统计一致字符串的数目	LeetCode 1684. 统计一致字符串的数目题解，Count the Number of Consistent Strings，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1684. 统计一致字符串的数目 统计一致字符串的数目 Count the Number of Consistent Strings 解题思路 位运算 数组 哈希表 字符串 计数

1684. 统计一致字符串的数目

🟢 Easy  🔖  位运算 数组 哈希表 字符串 计数  🔗 力扣 LeetCode

题目

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]

Output: 2

Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]

Output: 7

Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]

Output: 4

Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

• 1 <= words.length <= 10^4
• 1 <= allowed.length <= 26
• 1 <= words[i].length <= 10
• The characters in allowed are distinct.
• words[i] and allowed contain only lowercase English letters.

题目大意

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。

请你返回 words 数组中 一致字符串 的数目。

示例 1：

输入： allowed = "ab", words = ["ad","bd","aaab","baa","badab"]

输出： 2

解释： 字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。

示例 2：

输入： allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]

输出： 7

解释： 所有字符串都是一致的。

示例 3：

输入： allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]

输出： 4

解释： 字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。

提示：

• 1 <= words.length <= 10^4
• 1 <= allowed.length <= 26
• 1 <= words[i].length <= 10
• allowed 中的字符 互不相同 。
• words[i] 和 allowed 只包含小写英文字母。

解题思路

1. 存储允许字符：将 allowed 中的字符存储到一个 Set 数据结构中，以便快速判断某字符是否被允许。
2. 遍历数组 words：
   • 对于每个单词 word，检查其每个字符是否都在 Set 中。
   • 如果有任意一个字符不在 Set 中，则该单词不是一致字符串。
   • 如果检查通过，则计数器加一。
3. 返回结果：遍历完成后，返回计数器值。

复杂度分析

• 时间复杂度：O(a + m * l)，
  • 初始化 Set：O(a)，其中 a 是 allowed 的长度。
  • 遍历 words：
    • 外层循环遍历每个单词，O(m)，其中 m 是单词数组的长度。
    • 内层循环检查单词中的字符，O(l)，其中 l 是单词的平均长度。
  • 总复杂度为 O(a + m * l)。
• 空间复杂度：O(a)，其中 a 是 allowed 的长度，使用了一个 Set 来存储 allowed。

代码

::: code-tabs @tab 遍历

/**
 * @param {string} allowed
 * @param {string[]} words
 * @return {number}
 */
var countConsistentStrings = function (allowed, words) {
	let allowChar = new Set(allowed.split(''));
	let count = 0;

	for (let word of words) {
		let consistent = true;
		for (let char of word) {
			if (!allowChar.has(char)) {
				consistent = false;
				break;
			}
		}
		if (consistent) {
			count++;
		}
	}
	return count;
};

@tab 内置函数

var countConsistentStrings = function (allowed, words) {
	const allowChar = new Set(allowed);
	return words.filter((word) => [...word].every((char) => allowChar.has(char)))
		.length;
};

:::

相关题目

题号	标题	题解	标签	难度	力扣
2506	统计相似字符串对的数目		位运算 数组 哈希表 2+	🟢	🀄️ 🔗