小美的密码
美团 2024-08-10 后端笔试编程题
题目描述
小美准备登录美团，需要输入密码。她忘记了密码，只记得密码可能是 n 个字符串 中的一个。小美会按照密码长度从小到大依次尝试每个字符串；对于相同长度的字符串， 她会随机尝试，并且相同的密码只会尝试一次。 小美想知道，她最少需要尝试多少次才能登录成功，最多需要尝试多少次。 小美不会重新尝试已经尝试过的字符串，成功登录后会立即停止尝试。
输入格式
第一行一个整数 n，代表密码字符串的个数。 第二行一个只由小写字母组成的字符串 s，代表正确的密码。 接下来 n 行，每行一个字符串，代表小美记得的密码。
输出格式
在一行上输出两个整数，表示最少和最多尝试次数。
示例
示例 1
输入：
4
ab
abc
ab
ac
ac
输出：
1 2
说明：
正确密码是 ab（长度 2）。长度为 2 的不同密码有 ab、ac 两个。
- 最少：随机顺序里第一个就试到
ab→ 1 次； - 最多：先试
ac再试ab→ 2 次。
注意 ac 出现了两次，但相同的密码只试一次；长度 3 的 abc 不会被试到。
解题思路
第一步：长度小的密码一定会被全部试完
她按长度从小到大尝试，所以长度比 |s| 小的所有不同密码都会试一遍
（它们必然全错）。设这部分的数量为 step。
第二步：正确密码那一「层」决定成败
长度恰好等于 |s| 的不同密码有 d 个，其中一个是正确的。
她在这个集合里随机试：
- 最少：运气最好，第 1 个就中 →
step + 1； - 最多：运气最差，试到最后一个 →
step + d。
第三步：按长度分组去重
用「长度 → 该长度下不同字符串的集合」统计。 从小到大遍历长度，遇到包含正确密码的那一组就算出答案。
完整代码实现
算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入
import sys
from collections import defaultdict
def solve() -> None:
"""按长度分组去重，统计比正确密码短的个数"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
s = data[1]
words = data[2:2 + n]
by_len = defaultdict(set)
for w in words:
by_len[len(w)].add(w)
step = 0
mn = mx = -1
for length in sorted(by_len):
group = by_len[length]
if s in group:
mn = step + 1
mx = step + len(group)
break
step += len(group)
sys.stdout.write(f"{mn} {mx}\n")
if __name__ == "__main__":
solve()
示例推演
输入 n=4，正确密码 ab，记得的密码为 abc、ab、ac、ac：
| 长度 | 去重后的集合 | 说明 |
|---|---|---|
| 2 | {ab, ac} | 正确密码在这里 → 停止 |
| 3 | {abc} | 不会尝试（已经成功） |
step = 0（没有比 2 更短的长度），d = 2。
所以最少 0 + 1 = 1 次，最多 0 + 2 = 2 次。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 分组去重 + 排序 | O(总长度 + 不同长度 log) | O(总长度) | 推荐 |
易错点总结
1. 忘记去重
同一个密码可能出现多次，但「相同的密码只会尝试一次」， 所以必须用集合去重，否则最多尝试次数会算大。
2. 以为长度大的密码也会被尝试
成功登录后立即停止，所以长度大于 |s| 的密码一次都不会试。
3. 输出格式
两个整数在同一行，用空格分隔（不是换行）。
扩展思考
- 如果把「按长度排序」改成「按字典序」，就换成另一套统计口径。
- 这类「最坏/最好情况下的试错次数」是典型的去重 + 计数模型。