题目描述与示例
题目描述
小强正在参加《密室逃生》游戏，当前关卡要求找到符合给定密码 K（升序的不重复小写字母组成）的箱子，并给出箱子编号，箱子编号为 1~N。
每个箱子中都有一个字符串 s，字符串由大写字母，小写字母，数字，标点符号，空格组成，需要在这些字符串中找出所有的字母，忽略大小写且去重后排列出对应的密码串，并返回匹配密码的箱子序号。
注意：满足条件的箱子不超过 1 个。
输入描述
第一行为表示密码 K 的字符串
第二行为一系列箱子 boxes，为字符串数组样式，以空格分隔
箱子 N 数量满足 1<=N<=10000，代表每一个箱子的字符串 s 的长度满足 0 <= s.length <= 50，密码为仅包含小写字母的升序字符串，且不存在重复字母，密码 K 长度满足1 <= K.length <= 26
输出描述
返回对应箱子编号，如不存在符合要求的密码箱，则返回-1
补充说明
箱子中字符拼出的字符串与密码的匹配忽略大小写，且要求与密码完全匹配，如密码 abc 匹配 aBc，但是密码 abc 不匹配 abcd
示例 1
输入
abc
s,sdf134 A2c4b
输出
2
说明
第 2 个箱子中的 Abc，符合密码 abc
示例 2
输入
abc
s,sdf134 A2c4bd 523[]
输出
-1
说明
第 2 个箱子中的 Abcd，与密码不完全匹配，不符合要求。
解题思路
本题思路非常直接。由于密码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"不能匹配，那么应该如何修改代码？
代码
Python
# 题目：2023Q1A-寻找关键钥匙
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：哈希集合
# 代码有看不懂的地方请直接在群上提问
K = input() # 输入密码字符串K
boxes = input().split() # 输入箱子字符串数组boxes
ans = -1 # 初始化答案为-1
K_set = set(K) # 得到密码字符串所对应的集合
# 遍历boxes字符串中的所有索引i和字符串s
for i, s in enumerate(boxes):
# 得到字符串s中所有字母的集合，其中大写字母均转化为小写字母
s_set = {ch.lower() for ch in s if ch.isalpha()}
if K_set == s_set: # 如果该集合与密码集合相等，则得到了符合要求的箱子编号
ans = i+1 # 注意箱子编号是从1开始的
break # 因为只有一个箱子满足要求，所以此时直接退出循环即可
print(ans)
Java
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String K = scanner.nextLine(); // 输入密码字符串K
String[] boxes = scanner.nextLine().split(" "); // 输入箱子字符串数组boxes
int ans = -1; // 初始化答案为-1
HashSet<Character> K_set = new HashSet<>(); // 得到密码字符串所对应的集合
for (char ch : K.toCharArray()) {
K_set.add(ch);
}
// 遍历boxes字符串中的所有索引i和字符串s
for (int i = 0; i < boxes.length; i++) {
String s = boxes[i];
HashSet<Character> s_set = new HashSet<>(); // 得到字符串s中所有字母的集合，其中大写字母均转化为小写字母
for (char ch : s.toCharArray()) {
if (Character.isLetter(ch)) {
s_set.add(Character.toLowerCase(ch));
}
}
if (K_set.equals(s_set)) { // 如果该集合与密码集合相等，则得到了符合要求的箱子编号
ans = i + 1; // 注意箱子编号是从1开始的
break; // 因为只有一个箱子满足要求，所以此时直接退出循环即可
}
}
System.out.println(ans);
scanner.close();
}
}
C++
“`C++
#include <iostream>
#include <sstream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string K;
getline(cin, K); // 输入密码字符串K
<pre><code>string line;
getline(cin, line);
stringstream ss(line);
vector<string> boxes;
string box;
while (ss >> box) {
boxes.push_back(box);
} // 输入箱子字符串数组boxes
int ans = -1; // 初始化答案为-1
// 得到密码字符串所对应的集合
unordered_set<char> K_set(K.begin(), K.end());
// 遍历boxes字符串中的所有索引i和字符串s
for (int i = 0; i < boxes.size(); i++) {
string s = boxes[i];
unordered_set<char> s_set;
// 得到字符串s中所有字母的集合，其中大写字母均转化为小写字母
for (char ch : s) {
if (isalpha(ch)) {
s_set.insert(tolower(ch));
}
}
if (K_set == s_set) { // 如果该集合与密码集合相等，则得到了符合要求的箱子编号
ans = i + 1; // 注意箱子编号是从1开始的
break; // 因为只有一个箱子满足要求，所以此时直接退出循环即可
}
}
cout << ans << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(k+NM)。
空间复杂度：O(k+M)。
其中N为boxes的长度，M为s的平均长度，k为K的长度。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
