提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode0420. 强密码检验器(difficult)

密码密码 检验
2023-09-14 09:01:30 时间

目录

1. 题目描述

2. 思路：分类讨论

3. 官解：分类讨论

3. 代码实现

1. 题目描述

如果一个密码满足下述所有条件，则认为这个密码是强密码：

  • 由至少 6 个，至多 20 个字符组成。
  • 至少包含 一个小写 字母，一个大写 字母，和 一个数字 。
  • 同一字符 不能 连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 如果满足其他条件也可以算是强密码)。

给你一个字符串 password ，返回 将 password 修改到满足强密码条件需要的最少修改步数。如果 password 已经是强密码，则返回 0 。

在一步修改操作中，你可以：

  • 插入一个字符到 password ，
  • 从 password 中删除一个字符，或
  • 用另一个字符来替换 password 中的某个字符。

示例 1：

输入：password = "a"
输出：5

示例 2：

输入：password = "aA1"
输出：3

示例 3：

输入：password = "1337C0d3"
输出：0

提示：

  • 1 <= password.length <= 50
  • password 由字母、数字、点 '.' 或者感叹号 '!'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/strong-password-checker
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 思路：分类讨论

        如果一个代码需要修复，需要考虑：

  1. 采取什么操作：删除，插入，还是修改？
  2. 哪个位置
  3. 如果是插入或修改的话，插入什么或者修改成什么

        目的是所需要修复的次数最小。

        第一感是能不能用动态规划？但是没有看出什么最优子问题结构以及重叠子问题的特征。先从启发性的角度考虑一下。

        什么情况下会需要插入，什么情况下会需要修改呢？

        首先，应该只有在原有字符串长度不足的时候才需要插入操作。其余情况下没有做插入操作的必然性。从尽量缩小搜索空间的角度来说，在字符串足够长的情况下没有必要考虑插入操作。

        其次，删除操作仅在长度超过20个字符时才需要。

        基于以上考虑，密码修改可以归结为：

  • (1)，如果原字符串长度不足的话，需要采取插入操作。插入操作所需要的次数，可以认为单纯地就是6-len(password)，因为插入操作具有足够的自由度肯定可以避免在插入操作处"3个及以上连续相同字符或者非法字符"的情况
  • (2)，如果原字符串长度超过20的话，需要采取删除操作。删除操作所需要的次数，可以认为单纯地就是len(password)-20。
  • (3)，如果是非法字符的话需要修改，修改次数即非法字符个数。
  • (4)，如果密码中存在3个及以上连续相同合法字符的情况的话，则执行修改操作。注意，连续非法字符的话不需要特别考虑 
  • (5),  如果原始字符串中没有大写、或者没有小写、或者没有数字的话，需要分解增加一次修改 

        password中的3个及以上连续相同字符的情况中（当然这里只需要考虑连续的合法字符，连续的非法字符如上所述逐个修改掉即可），很显然，3~5个连续时从中间抽1个修改掉即可，6~8个连续时从中间抽2个修改掉即可，以下依此类推，即长度为k>=3的连续相同字符只需要修改即可。

        启发式思路能够通常能够解决绝大部分问题，并取得相当好的近似结果。但是，如果想要保证最优结果，则需要无遗漏地考虑清楚所有各种corner case。

        以上所述的这些操作，有些是重复的。

        比如说"aaaB1"，将长度不足和连续字符串的修改分开来考虑了，因此得出的结果为2。但是，事实上只需要在3个a之间插入一个别的合法字符就起到了一箭双雕的效果。

        类似的，在一个长度合法的字符中对于非法字符可以仅采用修改的方式进行处理，但是一个超出20个字符的密码如果存在非法字符，很显然，删除能起到一箭双雕的效果。

        如此等等，要列举出所有可能的corner-case以取得最优结果非常困难。

        。。。

        经过数小时的奋斗，若干次提交，通过了90%的Testcase，最终终于失去了耐心。摘录官解如上，供感兴趣的小伙伴参考。

        本以为应该有什么特别牛B的解法，结果官解也是分类讨论。思路大抵相近（后面在以上考虑的基础上考虑了很多情况，但是最终没有通过测试，懒得再写上去了），但是确实没有信心能够把这所有的情况考虑穷尽。。。

3. 官解：分类讨论

        根据题目中的要求，我们可以将给定的字符串按照长度分成三类，进行分类讨论，即：

  • 长度严格小于 6；
  • 长度在 [6, 20] 范围内；
  • 长度严格大于 20;

        题目中给定的操作有三种，即：（1）添加一个字符；（2）替换一个字符；（3）删除一个字符。下面我们进行分类讨论，为了方便叙述，记给定字符串的长度为 n。

case1: 

        当给定的字符串长度严格小于 6 时，我们可以发现「删除一个字符」的操作是没有意义的，因为为了使得长度满足要求，我们需要至少添加 6-n个字符，而每使用「删除一个字符」的操作，我们就需要一次额外的「添加一个字符」的操作来保证长度。由于我们「删除一个字符」的目的只可能是因为该字符连续出现了三次或以上，因此我们不妨在原本被删除的字符的两侧均「添加一个字符」，使用相同次数的操作达到同样（或者更好）的结果。

        这样一来，如果字符串中出现不超过 4 个连续相同的字符，「替换一个字符」的操作也是没有意义的，因为「替换一个字符」的目的只可能是将连续相同的字符中间的某个字符替换成不同的字符，而这个数量不超过 4 时，我们在中间的位置添加一个不同的字符，也可以达到同样（或者更好）的结果。

        如果字符串中出现了 5 个连续相同的字符，那么「替换一个字符」的操作同样也是没有意义的。因为此时字符的种类只有一种，至少需要两次操作才能达到字符种类的要求。而我们在中间字符的两侧分别添加一个不同种类的字符，即可满足要求，并且操作次数最少。

        因此，我们证明出了在这种情况下，只有「添加一个字符」的操作是有意义的。因此，该操作的次数为 6 - n 与 3 - (3−(字符种类)) 中的较大值，即需要保证字符串长度和字符种类均满足要求。

case2:

        当给定的字符串长度在 [6, 20] 范围内，我们可以发现「添加一个字符」和「删除一个字符」的操作是没有意义的，这是因为在长度已经满足要求的前提下，我们只需要再满足：（1）包含全部的 3 类字符；（2）同一字符不连续出现 3 次。对于（1）而言，「删除一个字符」与该要求相反，而如果我们选择「添加一个字符」以增加字符的种类数，我们也可以「替换一个字符」，将当前数量较多的那一种字符替换成一种新的字符。对于（2）而言，如果「删除一个字符」，我们也可以将待删除的那个字符替换成与周围字符均不相同的字符；如果「添加一个字符」，我们也可以将添加位置两侧字符中的其中一个替换成待添加的字符，这样的结果均是一致的。

        因此，我们只需要考虑「替换一个字符」这一种操作就行了。对于连续的 k 个相同的字符，我们可以替换其中\left \lfloor \frac{k}{3} \right \rfloor个，使得不存在 3 个连续相同的字符（即每数 3 个字符就替换一次）。同时，我们还需要保证最终字符串包含全部的 3 类字符，因此替换操作的次数为 ((所有的 \left \lfloor \frac{k}{3} \right \rfloor之和)) 与 3 - (3−(字符种类)) 中的较大值。  

case3:

当给定的字符串长度严格大于 20 时，类似地我们可以发现「添加一个字符」的操作是没有意义的，但此时「替换一个字符」和「删除一个字符」这两种操作都是必不可少的。这是因为「删除一个字符」会起到调整（减少）字符串长度的作用，而当字符串长度满足要求，但仍然存在 3 个连续相同字符的时候，「替换一个字符」的操作在上一类讨论中被证明是比「删除一个字符」更优的。

那么我们首先可以分别求出「替换一个字符」和「删除一个字符」需要的次数。对于「替换一个字符」，与上一类讨论一样，需要的次数为 ((所有的\left \lfloor \frac{k}{3} \right \rfloor 之和))；而对于「删除一个字符」，需要的次数为 n-20。然而在删除字符的过程中，连续相同的字符数量也会变少。根据 k%3的值的不同，我们可以得出如下关于 \left \lfloor \frac{k}{3} \right \rfloor值的变化的结论：

  • 如果 k mod 3 = 0，那么删除 1 个字符后，\left \lfloor \frac{k}{3} \right \rfloor的值会减少 1，随后每删除 3 个字符，\left \lfloor \frac{k}{3} \right \rfloor的值会再减少 1；
  • 如果 k mod 3 = 1，那么删除 2 个字符后，\left \lfloor \frac{k}{3} \right \rfloor 的值会减少 1，随后每删除 3 个字符，\left \lfloor \frac{k}{3} \right \rfloor 的值会再减少 1；
  • 如果 k mod 3 = 2，那么每删除 3 个字符，\left \lfloor \frac{k}{3} \right \rfloor的值会减少 1。

        因此在删除字符时，我们优先从所有 k mod 3 = 0 的连续相同字符组中删除 1 个字符（这样可以使得「替换一个字符」的操作次数同时减少 1），其次从所有 k mod 3 = 1 的连续相同字符组中删除 2 个字符（这样可以使得「替换一个字符」的操作次数同时减少 11），最后每删除 3 个字符，可以使得「替换一个字符」的操作次数减少 1。

最终「删除一个字符」需要的次数为 n-20，「替换一个字符」需要的次数为 ((所有的 \left \lfloor \frac{k}{3} \right \rfloor 之和)) ，但可以通过删除字符省去若干次操作，最后得到的真正需要的操作次数还需要与 3 - (3−(字符种类)) 取较大值。

3. 代码实现

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        n = len(password)
        has_lower = has_upper = has_digit = False
        for ch in password:
            if ch.islower():
                has_lower = True
            elif ch.isupper():
                has_upper = True
            elif ch.isdigit():
                has_digit = True
        
        categories = has_lower + has_upper + has_digit

        if n < 6:
            return max(6 - n, 3 - categories)
        elif n <= 20:
            replace = cnt = 0
            cur = "#"

            for ch in password:
                if ch == cur:
                    cnt += 1
                else:
                    replace += cnt // 3
                    cnt = 1
                    cur = ch
            
            replace += cnt // 3
            return max(replace, 3 - categories)
        else:
            # 替换次数和删除次数
            replace, remove = 0, n - 20
            # k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作
            rm2 = cnt = 0
            cur = "#"

            for ch in password:
                if ch == cur:
                    cnt += 1
                else:
                    if remove > 0 and cnt >= 3:
                        if cnt % 3 == 0:
                            # 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作
                            remove -= 1
                            replace -= 1
                        elif cnt % 3 == 1:
                            # 如果是 k % 3 = 1 的组，那么存下来备用
                            rm2 += 1
                        # k % 3 = 2 的组无需显式考虑
                    replace += cnt // 3
                    cnt = 1
                    cur = ch
            
            if remove > 0 and cnt >= 3:
                if cnt % 3 == 0:
                    remove -= 1
                    replace -= 1
                elif cnt % 3 == 1:
                    rm2 += 1
            
            replace += cnt // 3

            # 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定
            use2 = min(replace, rm2, remove // 2)
            replace -= use2
            remove -= use2 * 2
            # 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量
            use3 = min(replace, remove // 3)
            replace -= use3
            remove -= use3 * 3
            return (n - 20) + max(replace, 3 - categories)

        

if __name__ == "__main__":
        
    sln = Solution()
    print(sln.strongPasswordChecker("a"))
    print(sln.strongPasswordChecker("aA1"))    
    print(sln.strongPasswordChecker("1337C0d3"))    
    print(sln.strongPasswordChecker("aaa123"))
    print(sln.strongPasswordChecker("aaa111"))    
    print(sln.strongPasswordChecker("aaaB1"))
    print(sln.strongPasswordChecker("ABABABABABABABABABAB1"))
    print(sln.strongPasswordChecker("bbaaaaaaaaaaaaaaacccccc"))

回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。) 

相关文章