题目

1684. 统计一致字符串的数目 - 力扣（LeetCode）

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

示例 1：

1
2
3
输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。

示例 2：

1
2
3
输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出：7
解释：所有字符串都是一致的。

示例 3：

1
2
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
2
3
4
5
class Solution {
    public int countConsistentStrings(String allowed, String[] words) {

    }
}

解题

字符集合的位表示

由于题目中说明字符串仅包含小写字母，我们可以使用位运算来表示字符串的字母集合。

通过一个 32 位整数mask来表示一个字符串的字母集合，其中每一位表示一个字母是否出现（如果一个字母出现了，那么将对应整数的位设1，否则就是0）。

构建 allowed 的字母集合 mask

首先，我们需要构建字符串 allowed 中出现的字母集合 mask。遍历 allowed 中的每个字符，将对应字母的二进制位置设为 1，得到一个整数 mask，表示 allowed 中出现的字母集合。

1
2
3
4
5
int mask = 0;
for (int i = 0; i < allowed.length(); i++) {
    char c = allowed.charAt(i);
    mask |= 1 << (c - 'a');
}

遍历 words 数组，统计一致字符串的数目

然后，我们遍历 words 数组，对于每个字符串 word，构建其字母集合 mask1，并通过 (mask1 | mask) == mask 判断 mask1 是否是 mask 的子集，如果是，则说明该字符串是一致字符串，将结果 res 增加。

1
2
3
4
5
6
7
8
9
10
11
int res = 0;
for (String word : words) {
    int mask1 = 0;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        mask1 |= 1 << (c - 'a');
    }
    if ((mask1 | mask) == mask) {
        res++;
    }
}

最后，返回统计得到的一致字符串的数目。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    // 获取字符串的字母集合 mask
    public int getMask(String word) {
        int mask = 0;
        int len = word.length();
        for (int i = 0; i < len; i++) {
            char c = word.charAt(i);
            mask |= 1 << (c - 'a');
        }
        return mask;
    }

    // 统计一致字符串的数目
    public int countConsistentStrings(String allowed, String[] words) {
        // 构建 allowed 的字母集合 allowedMask
        int allowedMask = getMask(allowed);
        int len = words.length;
        int count = 0;

        // 遍历 words 数组，统计一致字符串的数目
        for (int i = 0; i < len; i++) {
            // 获取当前字符串的字母集合 curMask
            int curMask = getMask(words[i]);
            // 判断 curMask 是否是 allowedMask 的子集
            if ((allowedMask | curMask) == allowedMask) {
                count++;
            }
        }

        // 返回一致字符串的数目
        return count;
    }
}