当前位置：首页 > news >正文

力扣(LeetCode)1832. 判断句子是否为全字母句(C++)

news 来源：原创 2024/5/5 21:05:36

哈希集合1

哈希集合记录 $26$ 个字母是否出现，一次遍历字符串，维护哈希集合，同时维护答案。遍历完成，仅当答案等于 $26$ ，句子是全字母句。

class Solution {
public:
    bool checkIfPangram(string sentence) {
        bool st[26] = {0};
        int ans = 0;
        for(auto &c:sentence){
            if(!st[c-'a']) ans++;
            st[c-'a'] = true;
        }
        if(ans<26) return false;
        return true;
    }
};

时间复杂度 : $O (n)$ ， $n$ 是字符串长度，遍历字符串时间复杂度 $O (n)$ 。
空间复杂度 : $O (∣ C ∣)$ ， $∣ C ∣ = 26$ 是小写字母总数，字符集的空间复杂度 $O (∣ C ∣)$ 。

哈希集合2

一次遍历字符串，维护哈希集合。之后遍历哈希集合，维护答案，仅当答案等于 $26$ ，句子是全字母句。

class Solution {
public:
    bool checkIfPangram(string sentence) {
        bool st[26] = {0};
        int ans = 0;
        for(auto &c:sentence) st[c-'a'] = true;
        for(int i = 0;i < 26;i++) ans+=st[i];
        if(ans<26) return false;
        return true;
    }
};

时间复杂度 : $O (n + ∣ C ∣)$ ， $n$ 是字符串长度， $∣ C ∣ = 26$ 是小写字母总数，遍历字符串和字符集时间复杂度 $O (n + ∣ C ∣)$ 。
空间复杂度 : $O (∣ C ∣)$ ，字符集的空间复杂度 $O (∣ C ∣)$ 。

位运算

将答案看成 $26$ 位二进制串，某一位为 $0$ ，则没有对应字符，某一位为 $1$ ，则有对应字符。遍历字符串，用或运算，将每一字母的存在性"或进"答案。仅当答案 $26$ 位全 $1$ ，句子是全字母句。

class Solution {
public:
    bool checkIfPangram(string sentence) {
        int ans = 0;
        for(auto &c:sentence) ans |= 1<<(c-'a');
        return ans == (1<<26) -1 ;
    }
};

时间复杂度 : $O (n)$ ， $n$ 是字符串长度，遍历字符串时间复杂度 $O (n)$ 。
空间复杂度 : $O (1)$ ，只使用常量级空间。