【LeetCode每日一题】【2023/1/19】2299. 强密码检验器 II

---

2299. 强密码检验器 II

LeetCode: 2299. 强密码检验器 II

$简单$

如果一个密码满足以下所有条件我们称它是一个 强 密码

• 它有至少 8 个字符。
• 至少包含 一个小写英文 字母。
• 至少包含 一个大写英文 字母。
• 至少包含 一个数字 。
• 至少包含 一个特殊字符 。特殊字符为"!@#$%^&*()-+" 中的一个。
• 它 不 包含 2 个连续相同的字符比方说 "aab" 不符合该条件但是 "aba" 符合该条件。

给你一个字符串 password 如果它是一个 强 密码返回 true否则返回 false 。

示例 1

输入password = "IloveLe3tcode!"
输出true
解释密码满足所有的要求所以我们返回 true 。

示例 2

输入password = "Me+You--IsMyDream"
输出false
解释密码不包含数字且包含 2 个连续相同的字符。所以我们返回 false 。

示例 3

输入password = "1aB!"
输出false
解释密码不符合长度要求。所以我们返回 false 。

提示

• 1 <= password.length <= 100
• password 包含字母数字和 "!@#$%^&*()-+" 这些特殊字符。

---

方法1模拟 + 哈希表

为多个条件创建布尔变量在遍历字符串的时候挨个去判断。

对于特殊字符 "!@#$%^&*()-+" 我们可以将其拆分全部写入一个 if 语句中也可以将这些字符全部存入哈希表中。在遍历字符串时去哈希表中查找字符。

#include <string>
#include <cctype>
#include <unordered_set>
using namespace std;

class Solution
{
public:
    bool strongPasswordCheckerII(const string &password)
    {
        if (password.size() < 8)
            return false;

        char pre = 0;
        bool lower = false, upper = false, digit = false, special = false;

        const unordered_set specials{'!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '+'};

        for (const char &c : password)
        {
            if (c == pre)
                return false;

            if (std::islower(c))
                lower = true;
            else if (std::isupper(c))
                upper = true;
            else if (std::isdigit(c))
                digit = true;
            else if (specials.find(c) != specials.end())
                special = true;

            pre = c;
        }
        return lower && upper && digit && special;
    }
};

若不采用哈希表则写为如下形式

else if (c == '!' || c == '@' || c == '#' || c == '$' || c == '%' || c == '^' || c == '&' || c == '*' || c == '(' || c == ')' || c == '-' || c == '+')
    special = true;

leetcode不支持C++20。若采用C++20及以上标准则可以用 contains 成员函数替换 specials.find(c) != specials.end()

else if(specials.contains(c))
    special = true;

复杂度分析

• 时间复杂度$O(n+|\Sigma |)$。其中n 为字符串 password 的长度$|\Sigma |$ 是特殊字符集合的长度。

  • 若采用哈希表的写法则 $O(|\Sigma |)$ 主要为建立哈希表的时间开销。查找哈希表的时间复杂度为 $O(1)$ 。
  • 若不采用哈希表而是对特殊字符挨个判断是否相等则这个操作等同于遍历特殊字符集也是需要 $O(|\Sigma |)$ 的时间。

• 空间复杂度$O(|\Sigma |)$。主要为存放特殊字符的哈希表的开销。

参考结果

Accepted
148/148 cases passed (0 ms)
Your runtime beats 100.00 % of cpp submissions
Your memory usage beats 6 % of cpp submissions (6.2 MB)

---

方法2模拟

考虑本题的特殊条件

password 包含字母数字和 "!@#$%^&*()-+" 这些特殊字符。

发现本题中的 password 除了上述的字符外不包含任何其它字符。于是对于本题来说可以直接将所有与特殊字符的操作去掉。如果一个字符不是字母、数字那么就直接默认为特殊字符。

#include <string>
#include <cctype>
using namespace std;

class Solution
{
public:
    bool strongPasswordCheckerII(const string &password)
    {
        if (password.size() < 8)
            return false;

        char pre = 0;
        bool lower = false, upper = false, digit = false, special = false;

        for (const char &c : password)
        {
            if (c == pre)
                return false;

            if (std::islower(c))
                lower = true;
            else if (std::isupper(c))
                upper = true;
            else if (std::isdigit(c))
                digit = true;
            else
                special = true;

            pre = c;
        }
        return lower && upper && digit && special;
    }
};

复杂度分析

• 时间复杂度$O(n)$。其中n 为字符串 password 的长度。由于去掉了对特殊字符的任何操作因此也没有了 $O(|\Sigma |)$ 。

• 空间复杂度$O(1)$。没有用到额外的、大小与输入数据有关的变量因此仅占用常数的额外空间。

---

方法3模拟 + 位运算

每个布尔变量都占用 8位 上述代码中4个布尔变量则需要占用 4 个字节。而表示真假两个状态实际上使用 1位 就够了。

我们可以采用 位掩码 的思路来实现。例如若字符 c 是小写字符则让最低位变为 1 若字符 c 是大写字符则让第2位变为 1以此类推。本题共需要表示4种状态则占用 4位 即可需要使用一个 8位 的 char 类型。

#include <string>
#include <cctype>
using namespace std;

class Solution
{
public:
    bool strongPasswordCheckerII(const string &password)
    {
        if (password.size() < 8)
            return false;

        unsigned char mask = 0;
        char pre = 0;
        for (const char &c : password)
        {
            if (c == pre)
                return false;

            if (std::islower(c))
                mask |= 0b0001;
            else if (std::isupper(c))
                mask |= 0b0010;
            else if (std::isdigit(c))
                mask |= 0b0100;
            else
                mask |= 0b1000;

            pre = c;
        }

        return mask == (1 | 2 | 4 | 8);
    }
};

位图也可以使用C++标准库中的 std::bitset 来实现。

复杂度分析

• 时间复杂度$O(n)$。其中n 为字符串 password 的长度 。

• 空间复杂度$O(1)$。没有用到额外的、大小与输入数据有关的变量因此仅占用常数的额外空间。