美文网首页
leetcode 1684 统计一致字符串的数目

leetcode 1684 统计一致字符串的数目

作者: 碎念枫子 | 来源:发表于2022-11-08 16:16 被阅读0次

    难度:简单

    给你一个由不同字符组成的字符串 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 <= 104
    • 1 <= allowed.length <= 26
    • 1 <= words[i].length <= 10
    • allowed 中的字符 互不相同
    • words[i]allowed 只包含小写英文字母。

    解题思路

    看到题目的时候内心觉得soeay,遍历一下words里面的每个字符串的字符是否包含在allowed里面就行了。

    代码

        public int countConsistentStrings(String allowed, String[] words) {
            //结果
            int count = 0;
            int index;
            for (String s : words) {
                for (index = 0; index < s.length(); index++) {
                    //判断一下是否在
                    if (!allowed.contains(s.charAt(index) + "")) {
                        break;
                    }
                }
                //如果循环没有被中断,那么index的值会等于字符串长度
                if (index == s.length()) {
                    count++;
                }
            }
            return count;
        }
    

    官方解题思路

    由题意可知,字符串 allowed 和字符串数组 words 中的所有字符串都只包含小写字母,因此我们可以用一个 32 位整数来表示一个字符串出现的字母集合(二进制,每一位代表一个字母,低到高为a~z,多余的位不管)。如果一个字母出现了,那么将对应整数的位设为 1。使用 mask 表示字符串 allowed 出现的字母集合。依次遍历字符串数组 words,用mask1来表示每个字符串的包含的字母集合,如果每个字符串的mark1和mask的或运算等于mask,说明mark1的字符集被mask包含。

    这样效率是我的代码的四倍,厉害哦~

    代码

    public int countConsistentStrings2(String allowed, String[] words) {
                //先算出allowed的字符集,也就是第一位的1代表a,第二位的1代表b。。。
            int mask = 0;
            for (int i = 0; i < allowed.length(); i++) {
                char c = allowed.charAt(i);
                mask |= 1 << (c - 'a');
            }
            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++;
                }
            }
            return res;
        }
    

    相关文章

      网友评论

          本文标题:leetcode 1684 统计一致字符串的数目

          本文链接:https://www.haomeiwen.com/subject/qjwwtdtx.html