LeetCode 题解工作台
统计一致字符串的数目
给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。 请你返回 words 数组中 一致字符串 的数目。 示例 1： 输入： allowed = "ab", words = ["ad","…
5
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
一种比较直接的思路是，用哈希表或数组 记录 `allowed` 中的字符。然后遍历 `words` 数组，对于每个字符串 ，判断其是否由 `allowed` 中的字符组成。若是，答案加一。 时间复杂度 ，空间复杂度 。其中 为所有字符串的总长度，而 为 `allowed` 字符集的大小。本题中 $C \leq 26$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个由不同字符组成的字符串 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 <= 1041 <= allowed.length <= 261 <= words[i].length <= 10allowed中的字符 互不相同 。words[i]和allowed只包含小写英文字母。
解题思路
方法一：哈希表或数组
一种比较直接的思路是，用哈希表或数组 记录 allowed 中的字符。然后遍历 words 数组，对于每个字符串 ，判断其是否由 allowed 中的字符组成。若是，答案加一。
时间复杂度 ，空间复杂度 。其中 为所有字符串的总长度，而 为 allowed 字符集的大小。本题中 。
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
s = set(allowed)
return sum(all(c in s for c in w) for w in words)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m + n * k), where m is the length of allowed, n is the number of words, and k is the average word length, because each character is checked once. Space complexity is O(1) because the hash set or bitmask uses a fixed size of at most 26 bits for lowercase letters. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Expect recognition of the array scanning plus hash lookup pattern.
- question_mark
Look for discussion on avoiding nested loops by using set or bitmap membership checks.
- question_mark
Check if candidate handles edge cases like empty words or full alphabet allowed strings.
常见陷阱
外企场景- error
Using nested loops without a hash set leads to O(n * k * m) complexity and TLE.
- error
Forgetting that allowed contains only distinct characters, so duplicates in allowed are irrelevant.
- error
Failing to handle words with characters outside 'a'-'z' could miscount consistent strings.
进阶变体
外企场景- arrow_right_alt
Return the list of consistent strings instead of the count.
- arrow_right_alt
Allow repeated characters in allowed and verify consistency without extra preprocessing.
- arrow_right_alt
Count strings consistent with multiple allowed sets and compare results.