Easy

题目描述

给你一个由不同字符组成的字符串 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 中的字符存入集合，然后遍历每个单词检查是否所有字符都在集合中
  2. 位掩码法：由于只有小写字母，可以用一个整数的位来表示字符集合，效率更高
  3. 字符数组标记法：用布尔数组标记哪些字符是允许的

推荐使用位掩码法，因为它在空间和时间上都更高效。

位掩码的核心思想：

  • 用一个 32 位整数的低 26 位表示 26 个字母是否被允许
  • 对于每个单词，检查其所有字符对应的位是否都为 1
  • 可以通过位运算快速判断字符串是否一致

具体实现：

  1. 遍历 allowed，为每个字符设置对应的位
  2. 对于每个单词，检查其字符是否都在允许的位掩码中
  3. 统计一致字符串的数量

代码实现

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        int mask = 0;
        // 构建允许字符的位掩码
        for (char c : allowed) {
            mask |= 1 << (c - 'a');
        }
        
        int count = 0;
        for (const string& word : words) {
            bool consistent = true;
            for (char c : word) {
                if ((mask & (1 << (c - 'a'))) == 0) {
                    consistent = false;
                    break;
                }
            }
            if (consistent) count++;
        }
        
        return count;
    }
};

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # 使用集合存储允许的字符
        allowed_set = set(allowed)
        
        count = 0
        for word in words:
            # 检查单词中的所有字符是否都在允许集合中
            if all(c in allowed_set for c in word):
                count += 1
        
        return count

public class Solution {
    public int CountConsistentStrings(string allowed, string[] words) {
        int mask = 0;
        // 构建允许字符的位掩码
        foreach (char c in allowed) {
            mask |= 1 << (c - 'a');
        }
        
        int count = 0;
        foreach (string word in words) {
            bool consistent = true;
            foreach (char c in word) {
                if ((mask & (1 << (c - 'a'))) == 0) {
                    consistent = false;
                    break;
                }
            }
            if (consistent) count++;
        }
        
        return count;
    }
}

var countConsistentStrings = function(allowed, words) {
    // 使用Set存储允许的字符
    const allowedSet = new Set(allowed);
    
    let count = 0;
    for (const word of words) {
        // 检查单词中的所有字符是否都在允许集合中
        if (word.split('').every(c => allowedSet.has(c))) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
哈希集合法O(A + W×L)O(A)
位掩码法O(A + W×L)O(1)

其中：

  • A = allowed 字符串的长度
  • W = words 数组的长度
  • L = 单个单词的平均长度

位掩码法的空间复杂度更优，只需要一个整数变量存储位掩码。

相关题目