E卷-猜字迷(100分)
猜字迷
问题描述
小王设计了一个简单的猜字谜游戏,游戏的谜面是一个错误的单词,比如 nesw,玩家需要猜出谜底库中正确的单词。猜中的要求如下: 对于某个谜面和谜底单词,满足下面任一条件都表示猜中:
- 变换顺序以后一样的,比如通过变换 w 和 e 的顺序,"nwes" 跟 "news" 是可以完全对应的;
- 字母去重以后是一样的,比如 "woood" 和 "wood" 是一样的,它们去重后都是 "wod"。
请你写一个程序帮忙在谜底库中找到正确的谜底。谜面是多个单词,都需要找到对应的谜底,如果找不到的话,返回 "not found"。
输入格式
- 第一行输入谜面单词列表,以 "," 分隔。
- 第二行输入谜底库单词列表,以 "," 分隔。
输出格式
- 匹配到的正确单词列表,以 "," 分隔。
- 如果找不到,返回 "not found"。
样例输入1
conection
connection,today
样例输出1
connection
样例解释1
无
样例输入2
bdni,wooood
bind,wrong,wood
样例输出2
bind,wood
样例解释2
无
数据范围
- 单词的数量 的范围:。
- 词汇表的数量 的范围:。
- 单词的长度 的范围:。
- 输入的字符只有小写英文字母,没有其他字符。
题解
注意这里实际考试的时候需要
对于第一个条件(变换顺序后一样),可以通过对单词进行排序来解决。如果两个单词排序后完全相同,那么它们就满足这个条件。
对于第二个条件(字母去重后一样),可以通过将单词转换为集合来解决。如果两个单词转换为集合后完全相同,那么它们就满足这个条件。
算法的主要步骤如下:
- 读取输入的谜面单词列表和谜底库单词列表。
- 对于每个谜面单词: a. 将单词排序并转换为字符串。 b. 将单词转换为集合并再转换为字符串。
- 对于谜底库中的每个单词,执行相同的操作。
- 比较处理后的谜面单词和谜底单词,如果满足任一条件,则匹配成功。
- 如果找到匹配,将匹配的单词添加到结果列表中;否则,添加 "not found"。
- 输出结果列表。
参考代码
- Python
# 输入获取
puzzles = input().split(",")
solutions = input().split(",")
# 算法入口
def solve(puzzles, solutions):
results = []
for puzzle in puzzles:
puzzle_set = "".join(sorted(set(puzzle)))
matched = False
for solution in solutions:
solution_set = "".join(sorted(set(solution)))
if puzzle_set == solution_set:
results.append(solution)
matched = True
# break # 如果一个谜面对应多个谜底,这里就不能break,如果一个谜面只对应一个谜底,那这里就要break,考试的时候都试下
if not matched:
results.append("not found")
return ",".join(results)
# 算法调用
print(solve(puzzles, solutions))
- C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_WORD_LEN 20
#define MAX_WORDS 1000
int compare(const void* a, const void* b) {
return (*(char*)a - *(char*)b);
}
void uniqueSort(char* str) {
int len = strlen(str);
qsort(str, len, sizeof(char), compare);
int i, j;
for (i = j = 0; i < len; i++)
if (i == 0 || str[i] != str[i-1])
str[j++] = str[i];
str[j] = '\0';
}
void solve(char puzzles[][MAX_WORD_LEN], int puzzle_count, char solutions[][MAX_WORD_LEN], int solution_count) {
for (int i = 0; i < puzzle_count; i++) {
char puzzle_set[MAX_WORD_LEN];
strcpy(puzzle_set, puzzles[i]);
uniqueSort(puzzle_set);
int matched = 0;
for (int j = 0; j < solution_count; j++) {
char solution_set[MAX_WORD_LEN];
strcpy(solution_set, solutions[j]);
uniqueSort(solution_set);
if (strcmp(puzzle_set, solution_set) == 0) {
printf("%s", solutions[j]);
matched = 1;
// break; // 如果一个谜面对应多个谜底,这里就不能break,如果一个谜面只对应一个谜底,那这里就要break,考试的时候都试下
}
}
if (!matched) {
printf("not found");
}
if (i < puzzle_count - 1) {
printf(",");
}
}
printf("\n");
}
int main() {
char puzzles[MAX_WORDS][MAX_WORD_LEN], solutions[MAX_WORDS][MAX_WORD_LEN];
char line[MAX_WORDS * MAX_WORD_LEN];
int puzzle_count = 0, solution_count = 0;
fgets(line, sizeof(line), stdin);
char* token = strtok(line, ",\n");
while (token != NULL) {
strcpy(puzzles[puzzle_count++], token);
token = strtok(NULL, ",\n");
}
fgets(line, sizeof(line), stdin);
token = strtok(line, ",\n");
while (token != NULL) {
strcpy(solutions[solution_count++], token);
token = strtok(NULL, ",\n");
}
solve(puzzles, puzzle_count, solutions, solution_count);
return 0;
}
- Javascript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let puzzles, solutions;
rl.question('', (puzzlesInput) => {
puzzles = puzzlesInput.split(',');
rl.question('', (solutionsInput) => {
solutions = solutionsInput.split(',');
console.log(solve(puzzles, solutions));
rl.close();
});
});
function solve(puzzles, solutions) {
const results = [];
for (const puzzle of puzzles) {
const puzzleSet = [...new Set(puzzle)].sort().join('');
let matched = false;
for (const solution of solutions) {
const solutionSet = [...new Set(solution)].sort().join('');
if (puzzleSet === solutionSet) {
results.push(solution);
matched = true;
// break; // 如果一个谜面对应多个谜底,这里就不能break,如果一个谜面只对应一个谜底,那这里就要break,考试的时候都试下
}
}
if (!matched) {
results.push("not found");
}
}
return results.join(',');
}
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] puzzles = scanner.nextLine().split(",");
String[] solutions = scanner.nextLine().split(",");
System.out.println(solve(puzzles, solutions));
scanner.close();
}
public static String solve(String[] puzzles, String[] solutions) {
List<String> results = new ArrayList<>();
for (String puzzle : puzzles) {
char[] chars = puzzle.toCharArray();
Arrays.sort(chars);
String puzzleSet = new String(chars);
puzzleSet = String.join("", new LinkedHashSet<>(Arrays.asList(puzzleSet.split(""))));
boolean matched = false;
for (String solution : solutions) {
chars = solution.toCharArray();
Arrays.sort(chars);
String solutionSet = new String(chars);
solutionSet = String.join("", new LinkedHashSet<>(Arrays.asList(solutionSet.split(""))));
if (puzzleSet.equals(solutionSet)) {
results.add(solution);
matched = true;
// break; // 如果一个谜面对应多个谜底,这里就不能break,如果一个谜面只对应一个谜底,那这里就要break,考试的时候都试下
}
}
if (!matched) {
results.add("not found");
}
}
return String.join(",", results);
}
}
- Cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <sstream>
using namespace std;
string solve(const vector<string>& puzzles, const vector<string>& solutions) {
vector<string> results;
for (const auto& puzzle : puzzles) {
string puzzleSet = puzzle;
sort(puzzleSet.begin(), puzzleSet.end());
puzzleSet.erase(unique(puzzleSet.begin(), puzzleSet.end()), puzzleSet.end());
bool matched = false;
for (const auto& solution : solutions) {
string solutionSet = solution;
sort(solutionSet.begin(), solutionSet.end());
solutionSet.erase(unique(solutionSet.begin(), solutionSet.end()), solutionSet.end());
if (puzzleSet == solutionSet) {
results.push_back(solution);
matched = true;
// break; // 如果一个谜面对应多个谜底,这里就不能break,如果一个谜面只对应一个谜底,那这里就要break,考试的时候都试下
}
}
if (!matched) {
results.push_back("not found");
}
}
string result;
for (size_t i = 0; i < results.size(); ++i) {
result += results[i];
if (i < results.size() - 1) result += ",";
}
return result;
}
int main() {
string line;
vector<string> puzzles, solutions;
getline(cin, line);
istringstream iss(line);
string word;
while (getline(iss, word, ',')) {
puzzles.push_back(word);
}
getline(cin, line);
istringstream iss2(line);
while (getline(iss2, word, ',')) {
solutions.push_back(word);
}
cout << solve(puzzles, solutions) << endl;
return 0;
}
#E卷##OD##OD机考#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记