leetcode
leetcode 351 ~ 400
强密码检验器

强密码检验器

难度:

标签:

题目描述

满足以下条件的密码被认为是强密码:

  • 由至少 6 个,至多 20 个字符组成。
  • 包含至少 一个小写 字母,至少 一个大写 字母,和至少 一个数字
  • 不包含连续三个重复字符 (比如 "Baaabb0" 是弱密码, 但是 "Baaba0" 是强密码)。

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

在一步修改操作中,你可以:

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

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示:

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

代码结果

运行时间: 28 ms, 内存: 0.0 MB


// Java Solution with Streams
 
// 思路:
// 1. 使用流计算各种条件,如字符类型缺失和重复字符长度。
// 2. 使用流简化条件判断和数据处理。
 
import java.util.stream.Stream;
 
public class StrongPasswordChecker {
 
    public int strongPasswordChecker(String password) {
        int n = password.length();
        long hasLower = password.chars().filter(Character::isLowerCase).count();
        long hasUpper = password.chars().filter(Character::isUpperCase).count();
        long hasDigit = password.chars().filter(Character::isDigit).count();
        int missingTypes = (hasLower > 0 ? 0 : 1) + (hasUpper > 0 ? 0 : 1) + (hasDigit > 0 ? 0 : 1);
 
        int[] replaceCount = {0};
        int[] one = {0}, two = {0};
        char[] chars = password.toCharArray();
 
        for (int i = 0; i < n;) {
            int j = i;
            while (i < n && chars[i] == chars[j]) i++;
            int len = i - j;
            if (len >= 3) {
                replaceCount[0] += len / 3;
                if (len % 3 == 0) one[0]++;
                else if (len % 3 == 1) two[0]++;
            }
        }
 
        if (n < 6) return Math.max(missingTypes, 6 - n);
        else if (n <= 20) return Math.max(missingTypes, replaceCount[0]);
        else {
            int delete = n - 20;
            replaceCount[0] -= Math.min(delete, one[0] * 1) / 1;
            replaceCount[0] -= Math.min(Math.max(delete - one[0], 0), two[0] * 2) / 2;
            replaceCount[0] -= Math.max(delete - one[0] - 2 * two[0], 0) / 3;
            return delete + Math.max(missingTypes, replaceCount[0]);
        }
    }
}
 

解释

方法:

这个题解的思路是分别检查密码是否满足三条规则: 1. 检查密码长度是否在6到20之间,计算需要插入或删除的字符数。 2. 检查密码是否包含小写字母、大写字母和数字,计算需要替换的字符数。 3. 将密码转换为连续字符的分组列表,迭代地应用删除操作,使得尽可能消除连续三个相同字符的情况。最后计算需要替换的分组数。 最终返回所需的最少修改步数,即删除操作数 + max(需要的类型替换数, 需要的分组替换数, 需要的插入数)。

时间复杂度:

O(n * num_required_deletes)

空间复杂度:

O(n)

代码细节讲解

🦆
在处理长度小于6或大于20的密码时,如何决定是插入、删除还是替换字符以达到最小修改步数?
对于长度小于6的密码,优先考虑插入操作,因为密码需要至少6个字符满足基本长度要求。如果同时缺少必要的字符类型(如大写、小写或数字),可以通过插入缺失类型的字符来同时解决两个问题。对于长度大于20的密码,首先考虑删除多余的字符以减少长度。在这个过程中,如果存在连续三个相同的字符,优先删除这些字符以减少需要的替换次数。替换操作主要用于同时调整字符类型和解决三个连续字符的问题,特别是当密码长度正好在6到20之间时。总的来说,选择哪种操作取决于同时满足所有密码规则的最小修改步数。
🦆
为什么在遍历分组列表时,选择删除字符数目为'group % 3'的分组?这样的选择对最终的修改步数有何影响?
选择删除字符数目为'group % 3'的分组是因为这种分组最容易通过删除一个字符就减少需要的替换次数。例如,一个长度为5的分组(group % 3 == 2)通过删除一个字符可以变为长度4,这样只需替换一次即可解决连续字符问题(而不是两次)。这种策略最小化了总的修改步数,因为它减少了连续字符组需要的替换次数。
🦆
在密码已经包含连续三个相同字符的情况下,如何确定是否需要替换字符或是删除字符来解决这一问题?
是否替换或删除字符取决于密码的总长度和连续字符的分组长度。如果密码长度超过20,优先考虑删除字符以减少总长度。如果密码长度较短或正好,考虑替换字符来打破连续性,尤其是当连续分组较短(如恰好3个字符)时。替换可以同时解决连续字符和字符多样性的问题。总体策略是选择可以同时最大程度减少修改次数和满足所有规则的操作。
🦆
如何保证在多种修改需求(如插入、删除、替换)并存时,选择的修改操作能确保总的修改次数最少?
为了确保总的修改次数最少,需要综合考虑所有规则并选择最优的操作策略。这通常涉及到优化操作的顺序和类型。例如,通过优先执行删除操作来调整长度,可以减少后续可能需要的替换次数。在插入时选择缺失的字符类型,可以同时解决长度和字符多样性的问题。最终,选择操作时要以满足所有密码规则的最小总修改次数为目标。具体实施时可能需要动态调整策略,根据当前密码的状态来选择最合适的操作。

相关问题