P2701. 寻找关键钥匙

解题思路

本题思路非常直接。由于密码 K 不包含重复字符，每一个箱子字符串 s 也要做去重处理，因此我们可以直接分别用哈希集合 K_set 和 s_set 来表示密码和箱子字符串。

主要步骤

遍历 boxes 中的每一个字符串 s，并且挑选出其中的所有字母 ch，并做 ch.lower() 即转为小写的处理，再将所有转为小写的字母构建为 s_set，再比较 K_set 和 s_set 是否完全相等即可。

若相等，则该箱子字符串 s 所对应的编号 i + 1（之所以 +1 是因为箱子的编号是从 1 而不是从 0 开始）即为答案。

思考

如果稍微修改本题的条件，即箱子字符串不做去重处理，即 s = "aa" 与 K = "a" 不能匹配，那么应该如何修改代码？

思路展开 代码的主线是：把密码和每个箱子字符串都规约成同一种形态——「去重后的小写字母集合」，然后直接比较相等。

• K_set = set(K)：题面保证密码由不重复的小写字母组成，转成集合后丢掉顺序信息没有影响，因为要比较的只是「含有哪些字母」。
• 对每个箱子字符串 s，集合推导式 {ch.lower() for ch in s if ch.isalpha()} 一次完成三件事：ch.isalpha() 过滤掉数字、标点和空格，只保留字母；ch.lower() 把大写统一转成小写，落实题面「忽略大小写」的要求；集合结构本身自动完成去重。
• 两个集合用 == 判断相等，相等即说明该箱子的字母（去重且不分大小写后）与密码完全一致。答案记为 i + 1，加 1 是因为题面箱子编号从 1 开始，而枚举下标从 0 开始。
• 题目保证满足条件的箱子不超过 1 个，所以命中后直接 break；若遍历完都没有命中，ans 保持初始值 -1 被输出。

复杂度分析 设箱子个数为 N，所有箱子字符串的总长度为 L，密码长度记为 |K|。

• 时间复杂度：O(|K| + L)。构建 K_set 是 O(|K|)；处理每个箱子时对字符串逐字符做过滤、转小写、插入集合，均摊都是 O(1)，全部箱子合计 O(L)；每次集合相等性比较至多涉及 26 个小写字母，可视为 O(1)，共比较 N 次。瓶颈在逐字符扫描所有箱子字符串上。
• 空间复杂度：K_set 与每个 s_set 最多各含 26 个字母，属于 O(1) 级别的附加空间（不计输入本身的存储）。