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

🟢   🔖  位运算 数组 哈希表 字符串 计数  🔗 力扣 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。

代码

遍历

/**
 * @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;
};

内置函数

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

相关题目

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