题解

本题要求从多个箱子中找出与给定密码相匹配的箱子编号。每个箱子内包含一个字符串，我们需要提取出所有字母字符，忽略大小写后按升序排列，若与给定密码完全一致，则返回该箱子的编号。如果没有匹配的箱子，则返回 -1。

思路分析

这道题的核心思路是：首先从每个箱子字符串中提取出所有的字母字符，忽略大小写并按升序排列，形成一个新的字符串。然后将这个新字符串与给定的密码进行比较，若完全一致，则认为该箱子匹配密码，返回其编号。如果没有匹配的箱子，则返回 -1。具体操作包括提取字母、转换大小写、排序，并通过逐个比较箱子中的密码与目标密码来实现匹配。

1. 密码提取：首先，我们需要提取每个箱子字符串中的字母字符，并忽略其他字符（如数字、标点、空格等）。对提取出的字母，忽略大小写并按照升序排列。

2. 匹配判断：如果提取出的字母字符串与给定的密码字符串完全一致（包括字母顺序和字符种类），则认为匹配成功，返回该箱子的编号。

3. 性能考虑：题目中提到最多有 10000 个箱子，每个箱子的字符串最大长度为 50，所以我们可以在时间复杂度允许的范围内逐个检查每个箱子。

4. 细节处理：

   • 忽略大小写的比较可以通过将所有字母转换为小写来实现。
   • 提取字母并排序后与密码直接比较。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

// 提取并排序字母
string extract_and_sort(const string& s) {
    string result;
    for (char c : s) {
        if (isalpha(c)) {
            result.push_back(tolower(c));
        }
    }
    sort(result.begin(), result.end());
    return result;
}

int main() {
    string password;
    cin >> password;  // 密码字符串
    cin.ignore();  // 忽略换行符
    string boxes_line;
    getline(cin, boxes_line);  // 读取箱子的字符串

    vector<string> boxes;
    size_t pos = 0;
    // 将输入的多个箱子分割成字符串
    while ((pos = boxes_line.find(" ")) != string::npos) {
        boxes.push_back(boxes_line.substr(0, pos));
        boxes_line.erase(0, pos + 1);
    }
    boxes.push_back(boxes_line);

    // 对密码进行处理
    string target_password = extract_and_sort(password);

    // 检查每个箱子
    for (int i = 0; i < boxes.size(); ++i) {
        string box_password = extract_and_sort(boxes[i]);
        if (box_password == target_password) {
            cout << i + 1 << endl;  // 返回箱子编号，从1开始
            return 0;
        }
    }

    // 如果没有匹配的箱子
    cout << -1 << endl;
    return 0;
}

python

def extract_and_sort(s):
    result = [c.lower() for c in s if c.isalpha()]
    return ''.join(sorted(result))

def find_matching_box(password, boxes):
    target_password = extract_and_sort(password)
    
    for i, box in enumerate(boxes):
        if extract_and_sort(box) == target_password:
            return i + 1  # 返回箱子编号，从1开始
    
    return -1

# 输入
password = input().strip()
boxes = input().strip().split()

# 输出匹配的箱子编号
print(find_matching_box(password, boxes))

java

import java.util.*;

public class Main {
    // 提取并排序字母
    public static String extractAndSort(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                result.append(Character.toLowerCase(c));
            }
        }
        char[] chars = result.toString().toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    public static int findMatchingBox(String password, String[] boxes) {
        String targetPassword = extractAndSort(password);
        
        for (int i = 0; i < boxes.length; i++) {
            if (extractAndSort(boxes[i]).equals(targetPassword)) {
                return i + 1;  // 返回箱子编号，从1开始
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String password = scanner.nextLine().trim();
        String[] boxes = scanner.nextLine().split(" ");
        
        // 输出匹配的箱子编号
        System.out.println(findMatchingBox(password, boxes));
    }
}

题目内容

小强正在参加《密室逃生》游戏，当前关卡要求找到符合给定 密码 $K$（升序的不重复小写字母组成） 的箱子，并给出箱子编号，箱子编号为 $1~N$ 。

每个箱子中都有一个 字符串 $s$ ，字符串由大写字母、小写字母、数字、标点符号、空格组成，需要在这些字符串中找到所有的字母，忽略大小写后排列出对应的密码串，并返回匹配密码的箱子序号。

提示：满足条件的箱子不超过 $1$ 个。

输入描述

第一行为 $key$ 的字符串，

第二行为箱子 $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$ ，与密码不完全匹配，不符合要求