单词重组(题解)

· · 题解

【题目描述】

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

【输入格式】

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

【输出格式】

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

【输入输出样例#1】

word.in word.out
2 2 caa cbb 3 cba cba cbb YES NO

【数据范围与约定】 对于100%的数据，1<=t<=10 ，1<=n<=1000 ,|s_i| 表示字符串的长度|s_i|<=1000且 所有字符串长度 的总和不超过1000

【题目大意】

给定n个字符串任意交换后可以全部相同。

【解题思路】

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

【本题错因】

没有判断字符串长度是否相同，因为这个题目是交换，而不是移动，所以只要是不一样长，就一定不相同

【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++) //遍历字符串s
                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;

【具体原理】

该代码首先读取输入的组数 t，然后依次处理每一组数据。

对于每一组数据，首先读取表示单词个数的值 n。然后使用一个 map 数据结构 mp 来存储每个字母出现的次数。对于每个单词，遍历字符串中的每个字符，并将字符加入到 mp 中，然后对应的计数器加一。这样，mp 中就存储了每个字母出现的频率。

接下来，遍历 mp 中的每个字符以及对应的计数器。对于计数器的值，如果不是 n￥ 的倍数，即该字母无法平均分配给每个单词，将 flag 设置为 1$，表示无法让每个单词相同。

最后，根据 flag 的值输出结果，如果 flag 为 1，则输出 “NO”，否则输出 “YES”。

这段代码的思路是通过统计每个字母的出现次数，判断每个字母是否能够平均分配给每个单词，从而判断能否让所有单词相同。