华为OD-2024年E卷-猜字谜 [100分]

问题描述

小王设计了一个简单的猜字谜游戏。谜面是一个写错的单词，比如 nesw，玩家要在谜底库里找出正确单词。

某个谜面和某个谜底，满足下面任一条件就算猜中：

1. 变换顺序以后一样（字母异位词）。比如交换 w 和 e，nwes 和 news 完全对应。
2. 按出现顺序去重以后一样。比如 woood 和 wood 去重后都是 wod。

谜面有多个单词，每个都要找对应谜底；找不到就填 not found。

输入

• 第一行：谜面单词列表，以 , 分隔
• 第二行：谜底库单词列表，以 , 分隔

输出

匹配到的正确单词列表，以 , 分隔。某个谜面找不到时，对应位置输出 not found。

示例

输入：

conection
connection,today

输出：

connection

conection 和 connection 去重后都是 coneti。

输入：

bdni,wooood
bind,wrong,wood

输出：

bind,wood

bdni 是 bind 的异位词；wooood 和 wood 去重后都是 wod。

思路

对每个谜底预处理两个签名，谜面来了直接比对：

• 异位词：把字母排序后的串当作签名。bdni 和 bind 都是 bdin。
• 去重：按第一次出现的顺序丢掉重复字母。wooood → wod，不是排序后的 dow。

每个谜面扫一遍谜底库，命中第一个就收下。库很小，两层循环足够。

复杂度：设谜面数 (R)、库大小 (A)、单词长度 (L)，时间 (O(R \cdot A \cdot L \log L))，主要花在排序上。

参考代码

Python3

import sys

def sorted_key(s):
    return ''.join(sorted(s))

def unique_key(s):
    seen = set()
    out = []
    for ch in s:
        if ch not in seen:
            seen.add(ch)
            out.append(ch)
    return ''.join(out)

def match(riddle, answers):
    rk_s, rk_u = sorted_key(riddle), unique_key(riddle)
    for ans in answers:
        if sorted_key(ans) == rk_s or unique_key(ans) == rk_u:
            return ans
    return 'not found'

def main():
    lines = [ln.strip() for ln in sys.stdin if ln.strip() != '']
    riddles = lines[0].split(',')
    answers = lines[1].split(',')
    print(','.join(match(r, answers) for r in riddles))

if __name__ == '__main__':
    main()

Java

import java.util.*;

public class Main {
    static String sortedKey(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }

    static String uniqueKey(String s) {
        StringBuilder sb = new StringBuilder();
        boolean[] seen = new boolean[256];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!seen[c]) {
                seen[c] = true;
                sb.append(c);
            }
        }
        return sb.toString();
    }

    static String match(String riddle, String[] answers) {
        String sk = sortedKey(riddle);
        String uk = uniqueKey(riddle);
        for (String ans : answers) {
            if (sortedKey(ans).equals(sk) || uniqueKey(ans).equals(uk)) {
                return ans;
            }
        }
        return "not found";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] riddles = sc.nextLine().split(",");
        String[] answers = sc.nextLine().split(",");
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < riddles.length; i++) {
            if (i > 0) out.append(',');
            out.append(match(riddles[i], answers));
        }
        System.out.println(out);
    }
}

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

vector<string> split(const string& s) {
    vector<string> out;
    string cur;
    stringstream ss(s);
    while (getline(ss, cur, ',')) out.push_back(cur);
    return out;
}

string sortedKey(string s) {
    sort(s.begin(), s.end());
    return s;
}

string uniqueKey(const string& s) {
    string out;
    bool seen[256] = {};
    for (unsigned char c : s) {
        if (!seen[c]) {
            seen[c] = true;
            out.push_back(c);
        }
    }
    return out;
}

string match(const string& riddle, const vector<string>& answers) {
    string sk = sortedKey(riddle), uk = uniqueKey(riddle);
    for (const auto& ans : answers) {
        if (sortedKey(ans) == sk || uniqueKey(ans) == uk) return ans;
    }
    return "not found";
}

int main() {
    string line1, line2;
    getline(cin, line1);
    getline(cin, line2);
    auto riddles = split(line1);
    auto answers = split(line2);
    for (size_t i = 0; i < riddles.size(); i++) {
        if (i) cout << ',';
        cout << match(riddles[i], answers);
    }
    cout << '\n';
    return 0;
}

C语言

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static void sorted_key(const char* s, char* out) {
    int n = (int)strlen(s);
    memcpy(out, s, n + 1);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (out[j] < out[i]) {
                char t = out[i];
                out[i] = out[j];
                out[j] = t;
            }
        }
    }
}

static void unique_key(const char* s, char* out) {
    int seen[256] = {0};
    int k = 0;
    for (int i = 0; s[i]; i++) {
        unsigned char c = (unsigned char)s[i];
        if (!seen[c]) {
            seen[c] = 1;
            out[k++] = s[i];
        }
    }
    out[k] = '\0';
}

int main(void) {
    char line1[4096], line2[4096];
    if (!fgets(line1, sizeof line1, stdin)) return 0;
    if (!fgets(line2, sizeof line2, stdin)) return 0;
    line1[strcspn(line1, "\r\n")] = 0;
    line2[strcspn(line2, "\r\n")] = 0;

    char* answers[256];
    int ac = 0;
    for (char* p = strtok(line2, ","); p && ac < 256; p = strtok(NULL, ",")) {
        answers[ac++] = p;
    }

    int first = 1;
    char* save = NULL;
    for (char* r = strtok_r(line1, ",", &save); r; r = strtok_r(NULL, ",", &save)) {
        char rk_s[256], rk_u[256];
        sorted_key(r, rk_s);
        unique_key(r, rk_u);
        const char* hit = "not found";
        for (int i = 0; i < ac; i++) {
            char ak_s[256], ak_u[256];
            sorted_key(answers[i], ak_s);
            unique_key(answers[i], ak_u);
            if (strcmp(ak_s, rk_s) == 0 || strcmp(ak_u, rk_u) == 0) {
                hit = answers[i];
                break;
            }
        }
        if (!first) putchar(',');
        first = 0;
        fputs(hit, stdout);
    }
    putchar('\n');
    return 0;
}

JSNode

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
const lines = [];
rl.on('line', (line) => lines.push(line));
rl.on('close', () => {
    const sortedKey = (s) => s.split('').sort().join('');
    const uniqueKey = (s) => {
        const seen = new Set();
        let out = '';
        for (const ch of s) {
            if (!seen.has(ch)) {
                seen.add(ch);
                out += ch;
            }
        }
        return out;
    };
    const riddles = lines[0].split(',');
    const answers = lines[1].split(',');
    const res = riddles.map((r) => {
        const sk = sortedKey(r), uk = uniqueKey(r);
        return answers.find((a) => sortedKey(a) === sk || uniqueKey(a) === uk) || 'not found';
    });
    console.log(res.join(','));
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strings"
)

func sortedKey(s string) string {
    a := []rune(s)
    sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
    return string(a)
}

func uniqueKey(s string) string {
    seen := map[rune]bool{}
    var b strings.Builder
    for _, ch := range s {
        if !seen[ch] {
            seen[ch] = true
            b.WriteRune(ch)
        }
    }
    return b.String()
}

func match(riddle string, answers []string) string {
    sk, uk := sortedKey(riddle), uniqueKey(riddle)
    for _, ans := range answers {
        if sortedKey(ans) == sk || uniqueKey(ans) == uk {
            return ans
        }
    }
    return "not found"
}

func main() {
    in := bufio.NewScanner(os.Stdin)
    in.Scan()
    riddles := strings.Split(in.Text(), ",")
    in.Scan()
    answers := strings.Split(in.Text(), ",")
    out := make([]string, len(riddles))
    for i, r := range riddles {
        out[i] = match(r, answers)
    }
    fmt.Println(strings.Join(out, ","))
}