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

无

数据范围

单词的数量 $N$ 的范围： $0 < N < 1000$ 。
词汇表的数量 $M$ 的范围： $0 < M < 1000$ 。
单词的长度 $P$ 的范围： $0 < P < 20$ 。
输入的字符只有小写英文字母，没有其他字符。

题解

注意这里实际考试的时候需要

对于第一个条件（变换顺序后一样），可以通过对单词进行排序来解决。如果两个单词排序后完全相同，那么它们就满足这个条件。

对于第二个条件（字母去重后一样），可以通过将单词转换为集合来解决。如果两个单词转换为集合后完全相同，那么它们就满足这个条件。

算法的主要步骤如下：

读取输入的谜面单词列表和谜底库单词列表。
对于每个谜面单词： 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))

#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);
    }
}

#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刷题笔记文章被收录于专栏

本专栏收集并整理了一些刷题笔记