LeetCode 题解工作台
强密码检验器
满足以下条件的密码被认为是强密码： 由至少 6 个，至多 20 个字符组成。 包含至少 一个小写 字母，至少 一个大写 字母，和至少 一个数字 。 不包含连续三个重复字符 (比如 "B aaa bb0" 是弱密码, 但是 "B aa b a 0" 是强密码)。 给你一个字符串 password ，返…
3
题型
3
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
答案摘要
class Solution: def strongPasswordChecker(self, password: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
满足以下条件的密码被认为是强密码：
- 由至少
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由字母、数字、点'.'或者感叹号'!'组成
解题思路
方法一
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate’s understanding of greedy algorithms and the ability to identify the most efficient solution to achieve password strength.
- question_mark
Check if the candidate handles edge cases, such as passwords already strong, too short, or containing invalid characters.
- question_mark
Evaluate how the candidate approaches the problem using invariant validation while considering each password condition separately.
常见陷阱
外企场景- error
Forgetting to handle edge cases, such as passwords shorter than 6 characters or those that already meet all conditions.
- error
Incorrectly applying character type checks, which may lead to unnecessary changes or missed modifications.
- error
Not considering efficient handling of consecutive repeating characters, which could lead to unnecessary deletions or changes.
进阶变体
外企场景- arrow_right_alt
Different constraints could be introduced, such as requiring a password to contain special characters, changing the acceptable length range, or adding more character type checks.
- arrow_right_alt
Handling passwords with non-alphanumeric characters like punctuation marks could be an additional challenge, testing edge case handling.
- arrow_right_alt
The problem could be modified to handle passwords that must meet different password strength levels, introducing more complex validation conditions.