LeetCode-1832. 判断句子是否为全字母句【哈希表,位运算】
题目描述:
全字母句 指包含英语字母表中每个字母至少一次的句子。
给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 。
如果是,返回 true ;否则,返回 false 。
示例 1:
输入:sentence = “thequickbrownfoxjumpsoverthelazydog”
输出:true
解释:sentence 包含英语字母表中每个字母至少一次。
示例 2:
输入:sentence = “leetcode”
输出:false
提示:
1 <= sentence.length <= 1000
sentence 由小写英语字母组成
https://leetcode.cn/problems/check-if-the-sentence-is-pangram/
解题思路一:用数组记录,一次遍历。
class Solution {
public:
bool checkIfPangram(string sentence) {
vector<int> cnt(26);
for(char c:sentence) ++cnt[c-'a'];
for(int freq:cnt) if(freq==0) return false;
return true;
}
};
时间复杂度:O(n)
空间复杂度:O©c=26
解题思路二:位运算,最终判断mask是否为26个1即(1 << 26) - 1
class Solution {
public:
bool checkIfPangram(string sentence) {
int mask = 0;
for (char& c : sentence) mask |= 1 << (c - 'a');
return mask == (1 << 26) - 1;
}
};
时间复杂度:O(n)
空间复杂度:O(1)
解题思路三:0