题解：P13428 [GCJ 2009 Qualification] Alien Language

· · 题解

题目描述

经过多年的研究，Google Labs 的科学家们发现了一种来自遥远星球的外星语言。这种外星语言非常独特，每个单词恰好由 L 个小写字母组成。此外，这种语言中恰好有 D 个单词。

在建立了该外星语言所有单词的字典后，科学家们的下一个重大突破是发现，外星人在过去十年间一直在向地球发送信息。不幸的是，由于两颗星球之间的距离遥远，这些信号在传输过程中被削弱，导致部分单词可能被误解。为了帮助科学家们解读这些信息，他们请你设计一个算法，能够判断给定模式下可能的解释数量。

一个模式恰好由 L 个符号组成。每个符号要么是一个小写字母（科学家们非常确定这就是那个字母），要么是由圆括号括起来的一组互不相同的小写字母。例如：(ab)d(dc) 表示第一个字母可以是 a 或 b，第二个字母一定是 d，第三个字母可以是 d 或 c。因此，模式 (ab)d(dc) 可能代表以下 4 种情况之一：add、adc、bdd、bdc。

思路分析

模拟即可，这道题的意思是判断外星语言中与给定模式匹配的单词数量。模式中的每个位置可能是固定字母，也可能是括号内的多个可选字母，我们需要检查每个单词是否符合模式的所有位置要求。

对于每个测试用例的模式，将其拆分为 L 个字符集（每个位置允许的字母）。例如，模式 (ab)d(dc) 会拆分为 {'a','b'}、{'d'}、｛‘d’,'c'}。

对每个单词，检查其每个位置的字母是否属于模式对应位置的字符集，若所有位置都符合则计数。

代码

#include <bits/stdc++.h>
using namespace std;
int L, D, N;
int main() {
    cin >> L >> D >> N;
    vector<string> words(D);
    for (int i = 0; i < D; ++i) {
        cin >> words[i];
    }
    for (int num = 1; num <= N; ++num) {
        string pattern;
        cin >> pattern;
        vector<unordered_set<char>> charSets(L);
        int pos = 0; 
        for (int i = 0; i < L; ++i) {
            if (pattern[pos] == '(') {
                pos++; 
                while (pattern[pos] != ')') {
                    charSets[i].insert(pattern[pos]);
                    pos++;
                }
                pos++; 
            } else {
                charSets[i].insert(pattern[pos]);
                pos++;
            }
        }
        int ans = 0;
        for (const string& word : words) {
            bool match = true;
            for (int i = 0; i < L; ++i) {
                if (charSets[i].find(word[i]) == charSets[i].end()) {
                    match = false;
                    break;
                }
            }
            if (match) {
                ans++;
            }
        }
        cout << "Case #" << num << ": " << ans << endl;
    }
    return 0;
}