题目描述
小强在参加《密室逃生》游戏,当前关卡需要找到符合给定密码 K
(升序的不重复小写字母组成)的箱子,并给出箱子编号。每个箱子中都有一个字符串,字符串由大写字母、小写字母、数字、标点符号、空格组成。需要在这些字符串中找到所有的字母,忽略大小写后排列出对应的密码,并返回匹配密码的箱子序号。满足条件的箱子不超过 1 个。
输入描述
- 第一行为
key
的字符串。 - 第二行为箱子
boxes
,为数组样式,以空格分隔。
输出描述
返回匹配的箱子编号。如果不存在包含要求的密码的箱子,则返回 -1
。
示例
输入:
abc
"1 aBc 2 def" "3 ghi 4 jkl"
输出:
1
解题思路
- 提取字母并排序:对于每个箱子中的字符串,提取所有字母并忽略大小写,然后按升序排序。
- 匹配密码:将排序后的字母序列与给定的密码
K
进行比较,如果匹配则返回对应的箱子编号。 - 返回结果:如果没有任何箱子匹配密码
K
,则返回-1
。
Java
import java.util.*;public class EscapeRoom {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String key = scanner.nextLine();String[] boxes = scanner.nextLine().split(" ");for (int i = 0; i < boxes.length; i++) {String box = boxes[i];String letters = extractAndSortLetters(box);if (letters.equals(key)) {System.out.println(i + 1);return;}}System.out.println(-1);}private static String extractAndSortLetters(String box) {StringBuilder letters = new StringBuilder();for (char c : box.toCharArray()) {if (Character.isLetter(c)) {letters.append(Character.toLowerCase(c));}}char[] chars = letters.toString().toCharArray();Arrays.sort(chars);return new String(chars);}
}
Python
def extract_and_sort_letters(box):letters = [c.lower() for c in box if c.isalpha()]letters.sort()return ''.join(letters)def find_matching_box(key, boxes):for i, box in enumerate(boxes):if extract_and_sort_letters(box) == key:return i + 1return -1key = input().strip()
boxes = input().strip().split()
print(find_matching_box(key, boxes))
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>using namespace std;string extractAndSortLetters(const string& box) {string letters;for (char c : box) {if (isalpha(c)) {letters.push_back(tolower(c));}}sort(letters.begin(), letters.end());return letters;
}int findMatchingBox(const string& key, const vector<string>& boxes) {for (size_t i = 0; i < boxes.size(); ++i) {if (extractAndSortLetters(boxes[i]) == key) {return i + 1;}}return -1;
}int main() {string key;getline(cin, key);string boxesLine;getline(cin, boxesLine);vector<string> boxes;size_t pos = 0;while ((pos = boxesLine.find(' ')) != string::npos) {boxes.push_back(boxesLine.substr(0, pos));boxesLine.erase(0, pos + 1);}boxes.push_back(boxesLine);cout << findMatchingBox(key, boxes) << endl;return 0;
}
JavaScript
function extractAndSortLetters(box) {const letters = box.split('').filter(c => /[a-zA-Z]/.test(c)).map(c => c.toLowerCase());letters.sort();return letters.join('');
}function findMatchingBox(key, boxes) {for (let i = 0; i < boxes.length; i++) {if (extractAndSortLetters(boxes[i]) === key) {return i + 1;}}return -1;
}const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let key;
let boxes;
let count = 0;rl.on('line', (line) => {if (count === 0) {key = line.trim();count++;} else {boxes = line.trim().split(' ');console.log(findMatchingBox(key, boxes));rl.close();}
});
复杂度分析
- 时间复杂度: O(N * M log M),其中 N 是箱子的数量,M 是每个箱子中字符串的长度。排序操作的时间复杂度为 O(M log M)。
- 空间复杂度: O(M),用于存储和排序每个箱子中的字母。
这些代码片段实现了根据给定的密码 K
,找到匹配的箱子编号,并返回结果。如果没有任何箱子匹配密码 K
,则返回 -1
。