LC 1832.Check if the Sentence Is Pangram

题目描述

这是 LeetCode 上的 1832. 判断句子是否为全字母句 ，难度为简单。

全字母句 指包含英语字母表中每个字母至少一次的句子。

给你一个仅由小写英文字母组成的字符串 sentence ，请你判断 sentence 是否为 全字母句 。

如果是，返回 true ；否则，返回 false 。

示例 1：

输入：sentence = "thequickbrownfoxjumpsoverthelazydog"
输出：true
解释：sentence 包含英语字母表中每个字母至少一次。

示例 2：

输入：sentence = "leetcode"
输出：false

提示：

• 1 <= sentence.length <= 1000
• sentence 由小写英语字母组成

解答

方法一：状态压缩

虽然也可以用数组来模拟哈希表，但是由于只出现小写英文字母，所以可以用一个整数来模拟哈希表，一个整数一共有 32 个二进制位，可以使用后 26 位来模拟是否出现，如果都出现了一次，最终整数的结果应该是 (1 << 26) - 1，也就是 1 左移 26 位之后减去 1 。

class Solution {
    public boolean checkIfPangram(String sentence) {
        int cnt = 0; // 用整数模拟哈希表
        for (int i = 0; i < sentence.length(); ++i) {
            cnt |= 1 << (sentence.charAt(i) - 'a'); // 将相应的二进制位置为1
        }
        return cnt == (1 << 26) - 1; // 返回最终结果
    }
}

• 时间复杂度：\(O(N)\)，其中 N 是 sentence 的长度。

• 空间复杂度：\(O(1)\)。

每题一图