1339 Ancient Cipher

題目連結

題目敘述

在古羅馬帝國，重要的訊息會經過兩道加密處理：

置換密碼（Substitution Cipher）

• 將訊息中的每個字母用另一個字母替換（例如：A → X，B → G…），同一個字 母永遠被換成同一個字母。 　例如：HELLO → AXIIB

排列密碼（Permutation Cipher）

• 將訊息的所有字母重新排列。 　例如：AXIIB → BIXIA

這兩種加密會依序套用：先置換，再排列。

你現在拿到兩個長度相同的字串：

• 第一個字串是加密後的訊息

• 第二個字串是你猜測的原始訊息

你要判斷是否有可能這個原始訊息，經過上述兩道加密後，變成了現在這個加密結果。

輸入格式

• 每組測資包含兩行字串(多筆)

• 第一行是加密後的訊息 a

• 第二行是猜測的原始訊息 b

• 兩行字串長度相同，最大長度為 100

• 字串僅包含 大寫英文字母 A–Z

輸出格式

• 對每一筆測資，輸出一行 YES 或 NO

• YES：代表可能是透過上述兩種加密方式加密而來

• NO：代表不可能是加密而來

解題思路

用 mapa, mapb 分別記錄 a, b 字元出現次數，freqa, freqb 紀錄字元出現頻率，用 sort() 排序後比較 freqa 、 freqb，相同代表不同字元出現頻率相同，輸出 "YES"。

程式碼

#include<bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    while (cin >> a >> b) {
        map<char, int> mapa, mapb;
        for (int i = 0; i < a.size(); i++) {
            if (mapa.find(a[i]) == mapa.end()) {
                mapa[a[i]] = 1;
            }else {
                mapa[a[i]] ++;
            }
            if (mapb.find(b[i]) == mapb.end()) {
                mapb[b[i]] = 1;
            }else {
                mapb[b[i]] ++;
            }
        }
        vector<int> freqa, freqb;
        for (const auto& [k, v] : mapa) {
            freqa.push_back(v);
        }
        for (const auto& [k, v] : mapb) {
            freqb.push_back(v);
        }
        sort(freqa.begin(), freqa.end());
        sort(freqb.begin(), freqb.end());
        for (int i = 0; i < freqa.size(); i++) {
            if (freqa[i] != freqb[i]) {
                cout << "NO\n";
                break;;
            }
            if (i == freqa.size() - 1) {
                cout << "YES\n";
            }
        }
    }
}