题目描述
满足以下条件的密码被认为是强密码：
- 由至少
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 <= 50password 由字母、数字、点 '.' 或者感叹号 '!' 组成
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 | class Solution:
def strongPasswordChecker(self, password: str) -> int:
def countTypes(s):
a = b = c = 0
for ch in s:
if ch.islower():
a = 1
elif ch.isupper():
b = 1
elif ch.isdigit():
c = 1
return a + b + c
types = countTypes(password)
n = len(password)
if n < 6:
return max(6 - n, 3 - types)
if n <= 20:
replace = cnt = 0
prev = '~'
for curr in password:
if curr == prev:
cnt += 1
else:
replace += cnt // 3
cnt = 1
prev = curr
replace += cnt // 3
return max(replace, 3 - types)
replace = cnt = 0
remove, remove2 = n - 20, 0
prev = '~'
for curr in password:
if curr == prev:
cnt += 1
else:
if remove > 0 and cnt >= 3:
if cnt % 3 == 0:
remove -= 1
replace -= 1
elif cnt % 3 == 1:
remove2 += 1
replace += cnt // 3
cnt = 1
prev = curr
if remove > 0 and cnt >= 3:
if cnt % 3 == 0:
remove -= 1
replace -= 1
elif cnt % 3 == 1:
remove2 += 1
replace += cnt // 3
use2 = min(replace, remove2, remove // 2)
replace -= use2
remove -= use2 * 2
use3 = min(replace, remove // 3)
replace -= use3
remove -= use3 * 3
return n - 20 + max(replace, 3 - types)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 | class Solution {
public int strongPasswordChecker(String password) {
int types = countTypes(password);
int n = password.length();
if (n < 6) {
return Math.max(6 - n, 3 - types);
}
char[] chars = password.toCharArray();
if (n <= 20) {
int replace = 0;
int cnt = 0;
char prev = '~';
for (char curr : chars) {
if (curr == prev) {
++cnt;
} else {
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
replace += cnt / 3;
return Math.max(replace, 3 - types);
}
int replace = 0, remove = n - 20;
int remove2 = 0;
int cnt = 0;
char prev = '~';
for (char curr : chars) {
if (curr == prev) {
++cnt;
} else {
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1) {
++remove2;
}
}
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1) {
++remove2;
}
}
replace += cnt / 3;
int use2 = Math.min(Math.min(replace, remove2), remove / 2);
replace -= use2;
remove -= use2 * 2;
int use3 = Math.min(replace, remove / 3);
replace -= use3;
remove -= use3 * 3;
return (n - 20) + Math.max(replace, 3 - types);
}
private int countTypes(String s) {
int a = 0, b = 0, c = 0;
for (char ch : s.toCharArray()) {
if (Character.isLowerCase(ch)) {
a = 1;
} else if (Character.isUpperCase(ch)) {
b = 1;
} else if (Character.isDigit(ch)) {
c = 1;
}
}
return a + b + c;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73 | class Solution {
public:
int strongPasswordChecker(string password) {
int types = countTypes(password);
int n = password.size();
if (n < 6) return max(6 - n, 3 - types);
if (n <= 20) {
int replace = 0, cnt = 0;
char prev = '~';
for (char& curr : password) {
if (curr == prev)
++cnt;
else {
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
replace += cnt / 3;
return max(replace, 3 - types);
}
int replace = 0, remove = n - 20;
int remove2 = 0;
int cnt = 0;
char prev = '~';
for (char& curr : password) {
if (curr == prev)
++cnt;
else {
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1)
++remove2;
}
replace += cnt / 3;
cnt = 1;
prev = curr;
}
}
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1)
++remove2;
}
replace += cnt / 3;
int use2 = min(min(replace, remove2), remove / 2);
replace -= use2;
remove -= use2 * 2;
int use3 = min(replace, remove / 3);
replace -= use3;
remove -= use3 * 3;
return (n - 20) + max(replace, 3 - types);
}
int countTypes(string& s) {
int a = 0, b = 0, c = 0;
for (char& ch : s) {
if (islower(ch))
a = 1;
else if (isupper(ch))
b = 1;
else if (isdigit(ch))
c = 1;
}
return a + b + c;
}
};
|