强密码检验器
难度:
标签:
题目描述
满足以下条件的密码被认为是强密码:
- 由至少
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的密码时,如何决定是插入、删除还是替换字符以达到最小修改步数?
▷🦆
为什么在遍历分组列表时,选择删除字符数目为'group % 3'的分组?这样的选择对最终的修改步数有何影响?
▷🦆
在密码已经包含连续三个相同字符的情况下,如何确定是否需要替换字符或是删除字符来解决这一问题?
▷🦆
如何保证在多种修改需求(如插入、删除、替换)并存时,选择的修改操作能确保总的修改次数最少?
▷