LeetCode 1684: Count the Number of Consistent Strings (Allowed-Set Membership Filtering)
LeetCode 1684StringHash SetFilteringToday we solve LeetCode 1684 - Count the Number of Consistent Strings.
Source: https://leetcode.com/problems/count-the-number-of-consistent-strings/
English
Problem Summary
Given a string allowed and an array words, a word is consistent if every character in it appears in allowed. Return the number of consistent words.
Key Insight
Convert allowed into a fast membership structure (boolean array or set). Then validate each word character-by-character; if any character is not allowed, reject that word immediately.
Brute Force and Limitations
Without preprocessing, each character check may scan the whole allowed string, making checks slower. Preprocessing allowed once gives O(1) average membership lookups.
Optimal Algorithm Steps
1) Build an allowed lookup table from allowed.
2) For each word, scan its characters.
3) If any character is not in lookup table, mark this word invalid and stop scanning it.
4) Count words that remain valid.
Complexity Analysis
Let total characters across all words be M.
Time: O(|allowed| + M).
Space: O(1) if using fixed-size 26 boolean array (or O(|allowed|) with a generic set).
Common Pitfalls
- Forgetting to stop early after finding an invalid character.
- Recomputing allowed lookup for every word.
- Treating duplicated characters in a word as special cases (they are naturally handled by membership checks).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countConsistentStrings(String allowed, String[] words) {
boolean[] ok = new boolean[26];
for (char c : allowed.toCharArray()) {
ok[c - 'a'] = true;
}
int count = 0;
for (String w : words) {
boolean valid = true;
for (int i = 0; i < w.length(); i++) {
if (!ok[w.charAt(i) - 'a']) {
valid = false;
break;
}
}
if (valid) count++;
}
return count;
}
}func countConsistentStrings(allowed string, words []string) int {
ok := make([]bool, 26)
for _, ch := range allowed {
ok[ch-'a'] = true
}
ans := 0
for _, w := range words {
valid := true
for _, ch := range w {
if !ok[ch-'a'] {
valid = false
break
}
}
if valid {
ans++
}
}
return ans
}#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
vector<bool> ok(26, false);
for (char c : allowed) ok[c - 'a'] = true;
int ans = 0;
for (const string& w : words) {
bool valid = true;
for (char c : w) {
if (!ok[c - 'a']) {
valid = false;
break;
}
}
if (valid) ans++;
}
return ans;
}
};from typing import List
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
ok = set(allowed)
ans = 0
for w in words:
valid = True
for ch in w:
if ch not in ok:
valid = False
break
if valid:
ans += 1
return ansvar countConsistentStrings = function(allowed, words) {
const ok = new Set(allowed);
let ans = 0;
for (const w of words) {
let valid = true;
for (const ch of w) {
if (!ok.has(ch)) {
valid = false;
break;
}
}
if (valid) ans++;
}
return ans;
};中文
题目概述
给定字符串 allowed 和字符串数组 words。如果一个单词中的每个字符都出现在 allowed 中，则该单词是“一致字符串”。返回一致字符串的数量。
核心思路
先把 allowed 预处理成可 O(1) 查询的结构（如布尔数组或哈希集合）。随后逐词逐字符检查，只要遇到非法字符就立刻判定该词不一致。
暴力解法与不足
若不做预处理，每次判断字符是否允许都去线性扫描 allowed，会产生重复开销。预处理后整体效率更高。
最优算法步骤
1）根据 allowed 构建查表结构。
2）遍历每个单词并逐字符检查。
3）若出现不在查表中的字符，立即判该词无效并跳出。
4）统计所有有效单词数量。
复杂度分析
设所有单词总字符数为 M。
时间复杂度：O(|allowed| + M)。
空间复杂度：若用 26 长度布尔数组为 O(1)；若用集合则为 O(|allowed|)。
常见陷阱
- 发现非法字符后没有及时终止当前单词检查。
- 每个单词都重复构建 allowed 查表，造成不必要开销。
- 误以为重复字符需要特殊处理（实际上按成员判断即可）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countConsistentStrings(String allowed, String[] words) {
boolean[] ok = new boolean[26];
for (char c : allowed.toCharArray()) {
ok[c - 'a'] = true;
}
int count = 0;
for (String w : words) {
boolean valid = true;
for (int i = 0; i < w.length(); i++) {
if (!ok[w.charAt(i) - 'a']) {
valid = false;
break;
}
}
if (valid) count++;
}
return count;
}
}func countConsistentStrings(allowed string, words []string) int {
ok := make([]bool, 26)
for _, ch := range allowed {
ok[ch-'a'] = true
}
ans := 0
for _, w := range words {
valid := true
for _, ch := range w {
if !ok[ch-'a'] {
valid = false
break
}
}
if valid {
ans++
}
}
return ans
}#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
vector<bool> ok(26, false);
for (char c : allowed) ok[c - 'a'] = true;
int ans = 0;
for (const string& w : words) {
bool valid = true;
for (char c : w) {
if (!ok[c - 'a']) {
valid = false;
break;
}
}
if (valid) ans++;
}
return ans;
}
};from typing import List
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
ok = set(allowed)
ans = 0
for w in words:
valid = True
for ch in w:
if ch not in ok:
valid = False
break
if valid:
ans += 1
return ansvar countConsistentStrings = function(allowed, words) {
const ok = new Set(allowed);
let ans = 0;
for (const w of words) {
let valid = true;
for (const ch of w) {
if (!ok.has(ch)) {
valid = false;
break;
}
}
if (valid) ans++;
}
return ans;
};
Comments