MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1339 - Ancient Cipher
AOAPC II

UVaOJ 1339 - Ancient Cipher

Chai
2021-11-24 0:00:00在线评测阅读 288

问题描述

p1339

原题链接:UVaOJ 1339 - Ancient Cipher

相关说明:本题为《算法竞赛入门经典(第2版)》例题 4-1

解法一:统计后排序

统计两个串中各个大写字母的出现次数,如果能够通过 substitution cipher 和 permutation cipher 加密解密,表明一定能找到 26 个字母之间的一一映射,且满足出现次数一致。因此这里对字母出现次数做一个排序,如果发现有出现次数无法匹配的情况,表明该字母找不到对方串中的字母进行映射,输出 NO.

C++
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;
}
Python
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
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz