刷题笔记合集🔗

猜字迷

问题描述

小王设计了一个简单的猜字谜游戏，游戏的谜面是一个错误的单词，比如 nesw，玩家需要猜出谜底库中正确的单词。猜中的要求如下： 对于某个谜面和谜底单词，满足下面任一条件都表示猜中：

1. 变换顺序以后一样的，比如通过变换 w 和 e 的顺序，"nwes" 跟 "news" 是可以完全对应的；
2. 字母去重以后是一样的，比如 "woood" 和 "wood" 是一样的，它们去重后都是 "wod"。

请你写一个程序帮忙在谜底库中找到正确的谜底。谜面是多个单词，都需要找到对应的谜底，如果找不到的话，返回 "not found"。

输入格式

1. 第一行输入谜面单词列表，以 "," 分隔。
2. 第二行输入谜底库单词列表，以 "," 分隔。

输出格式

• 匹配到的正确单词列表，以 "," 分隔。
• 如果找不到，返回 "not found"。

样例输入1

conection
connection,today

样例输出1

connection

样例解释1

无

样例输入2

bdni,wooood
bind,wrong,wood

样例输出2

bind,wood

样例解释2

无

数据范围

1. 单词的数量 的范围：。
2. 词汇表的数量 的范围：。
3. 单词的长度 的范围：。
4. 输入的字符只有小写英文字母，没有其他字符。

题解

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

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

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

算法的主要步骤如下：

1. 读取输入的谜面单词列表和谜底库单词列表。
2. 对于每个谜面单词： a. 将单词排序并转换为字符串。 b. 将单词转换为集合并再转换为字符串。
3. 对于谜底库中的每个单词，执行相同的操作。
4. 比较处理后的谜面单词和谜底单词，如果满足任一条件，则匹配成功。
5. 如果找到匹配，将匹配的单词添加到结果列表中；否则，添加 "not found"。
6. 输出结果列表。

参考代码

• 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(puz