问题描述
p1339原题链接：UVaOJ 1339 - Ancient Cipher
相关说明：本题为《算法竞赛入门经典（第2版）》例题 4-1
解法一：统计后排序
统计两个串中各个大写字母的出现次数，如果能够通过 substitution cipher 和 permutation cipher 加密解密，表明一定能找到 26 个字母之间的一一映射，且满足出现次数一致。因此这里对字母出现次数做一个排序，如果发现有出现次数无法匹配的情况，表明该字母找不到对方串中的字母进行映射，输出 NO.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <bits/stdc++.h> using namespace std; int main() { const int ALPHABET_NUM = 26; string s1, s2; while (cin >> s1 >> s2) { array<int, ALPHABET_NUM> cnt1 = {0}, cnt2 = {0}; for (auto c : s1) cnt1[c - 'A']++; for (auto c : s2) cnt2[c - 'A']++; sort(cnt1.begin(), cnt1.end()); sort(cnt2.begin(), cnt2.end()); bool encrypt = true; for (int i = 0; i < ALPHABET_NUM; ++i) if (cnt1[i] != cnt2[i]) { encrypt = false; break; } cout << (encrypt ? "YES" : "NO") << endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ALPHABET_NUM = 26 while True: try: s1, s2 = input(), input() cnt1 = [0 for _ in range(ALPHABET_NUM)] cnt2 = [0 for _ in range(ALPHABET_NUM)] for c in s1: cnt1[ord(c) - ord('A')] += 1 for c in s2: cnt2[ord(c) - ord('A')] += 1 cnt1, cnt2 = sorted(cnt1), sorted(cnt2) print("YES" if cnt1 == cnt2 else "NO") except EOFError: break |
