【LeetCode】Day177-统计一致字符串的数目

题目

1684. 统计一致字符串的数目【简单】

题解

用哈希表可以完成时间复杂度为O(mn)的解法，官解给的是用位运算的解法，时间复杂度可以优化为$O(n+\sum m_i)$

• 由于只包含小写字母，因为可以用32位整数来表示字符串出现的字母集合，记allowed中字母集合为mask
• 记words中某一个字符串字母集合为mask1，所以如果mask1∪mask=mask，即mask1中字母全在mask中，则表明该字符串是一致字符串
• 补充：java中取并集的操作应该怎么实现呢？用位或运算符 | ，见
  

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        int res=0,mask=0;
        //计算mask
        for(int i=0;i<allowed.length();i++){
            char ch=allowed.charAt(i);
            mask|=1<<(ch-'a');
        }
        for(String word:words){
            int mask1=0;
            //计算mask1
            for(int j=0;j<word.length();j++){
                char ch=word.charAt(j);
                mask1|=1<<(ch-'a');
            }
            //并集为mask，则说明为一致字符串
            if((mask1|mask)==mask)
                res++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：$O(n+\sum m_i)$

空间复杂度：$O(1)$