欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

uva 1339 Ancient Cipher

程序员文章站 2022-04-02 10:28:44
...

点击打开链接uva 1399

题意:给定两个长度分别为n的字符串,判断他们能否一一对应
思路:暴力
分析:
1 首先我们知道这两个字符串的长度最大为100并且相等
2 刚开始我的想法是对两个字符串排序,然后从头开始枚举判断。这个想法妥妥的过了样例,然而等到的确实一顿怒wa。下面举例证明我的思路是错误的
3 假设有两个字符串为ABBCFEA 和 CCGGHJB。排序后为AABBCEF和 BCCGGHJ如果按照我的思路那么我们从头开始枚举得到的是NO,但是实际上这个例子是YES。我们写出两个字符串中字母出现的次数的序列分别为22111和12211,那么我们对这个数字序列进行排序分别为11122和11122可以知道这个比较就可以得到YES

代码:

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 110;

bool ok(char *s1 , char *s2){
    int len = strlen(s1);
    int num1[maxn] , num2[maxn];
    memset(num1 , 0 , sizeof(num1));
    memset(num2 , 0 , sizeof(num2));
    for(int i = 0 ; i < len ; i++){
       num1[s1[i]-'A']++;
       num2[s2[i]-'A']++;
    }
    sort(num1 , num1+maxn);
    sort(num2 , num2+maxn);
    return !memcmp(num1 , num2 , sizeof(num1)) ? true : false;
}

int main(){
    char s1[maxn] , s2[maxn];
    while(scanf("%s" , s1) != EOF){
        scanf("%s" , s2);
        printf("%s\n" , ok(s1 , s2) ? "YES" : "NO");
    }
    return 0;
}