单词重组

· · 个人记录

题目

给你 n 组仅由小写字母组成的单词，第 i 组单词为si，你可以将 n 组单词中任意两个字母进行若干次交换，如果经过若干次交换后是否能够让 n 个单词全部相同 ，如果可以输出"YES",否则出"NO" 。

【输入格式】

第一行输入一个正整数t，代表t组数据。 每组数据包含，一个 n 表示 n 个单词。 以及 n 个具体的单词，每个单词占一行。

【输出格式】

输出 n 组，"YES" 或者 "NO" 。

解题思路

使用桶或者ma处理每个字母，然后判断每个字母的个数是否是n的倍数。如果出现一个字母不是n的倍数那么就无法保证交换后的字符串不同。

自己的错误代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool same(string a, string b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;
}//判断两个字符串是否相同
string r(int n, vector<string> & words) {
    //遍历前n-1个单词，将其与第n个单词进行比较
    for(int i = 0; i < n - 1; i++) {
        if(!same(words[i], words[n-1])) {
            return "NO";
        }
        else 
            return "YES";
    }

}//判断是否能够重组使所有单词相同
int main(){
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector <string> words(n);
        for(int i = 0; i < n; i++){
            cin >> words[i];
        }
        // 判断是否能够重组使所有单词相同
        string result = r(n, words);
        cout << result << endl;
    }
    return 0;
}

run了一下，可以发现全是“NO”

就-离-谱

AC代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    //freopen("word.in", "r", stdin);
    //freopen("word.out", "w", stdout);
    int t, n;
    string s;
    cin >> t;
    while (t--) {
        cin >> n;
        map<char, int> mp;
        for (int i = 1; i <= n; i++) {
            cin >> s;
            for (int j = 0; j < s.size(); j++)
                mp[s[j]]++; //建立映射
        }
        int flag = 0;
        for (auto it : mp)
            if (it.second % n != 0) { //判断字母的个数是否位n的倍数
                flag = 1; //同一字符无法平均分配。
                break;
            }
        if (flag)cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}

Tips:

for (auto it : mp) 为c++14标准 需要加入-std=c++14 其中 it 为 iterator 指迭代器