题解 | #查找兄弟单词#

1. 用multiset<string>存储找到的兄弟单词，即可自动排序，之所以不用set是因为题目说明“字典中可能有重复元素”，因此兄弟单词中也可能有重复元素
2. 如何判断字典中的元素是否为 x 的兄弟单词？题目说了可以移动无限次，就不能用交换字母的方法来比较，因为很难穷举，应该直接比较两个单词中对应字母的出现次数即可，也就是说，设单词w1中字母a~z出现的次数分别为w1[0]~w[25]，单词w2为w2[0]~w2[25]，直接比较数组w1与w2是否相同即可，还要加上 w1 != w2（兄弟单词不能相同）
3. 时间复杂度O(NlogN)，空间O(N)

#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <string>
using namespace std;

struct Word
{
    string s;
    vector<int> w; // 哈希数组，w[0]~w[25]对应s中a~z的数量
};

bool isEqual(vector<int>& w1, vector<int>& w2) // 比较两个哈希数组是否相同
{
    for (int i = 0; i < 26; ++i)
    {
        if (w1[i] != w2[i])
            return false;
    }
    return true;
}

int main() {
    // 读取字典
    int n, k;
    cin >> n;
    string s;
    vector<Word> v(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i].s;
        vector<int> temp(26, 0);
        for (auto c : v[i].s)
            temp[c - 'a']++;
        v[i].w.assign(temp.begin(), temp.end());
    }
    // 读取 x 和 k
    struct Word x;
    cin >> x.s >> k;
    vector<int> temp(26, 0);
    for (auto c : x.s)
        temp[c - 'a']++;
    x.w.assign(temp.begin(), temp.end());
    // 找兄弟单词，插入multiset（字典有重复元素）
    multiset<string> bro;
    for (auto word : v)
    {
        if (word.s != x.s && isEqual(word.w, x.w))
            bro.insert(word.s);
    }
    cout << (int)bro.size() << endl;
    // 输出第 k 个兄弟单词
    int cnt = 1;
    for (auto s : bro)
    {
        if (cnt == k)
        {
            cout << s;
            break;
        }
        cnt++;
    }
    cout << endl;
}
// 64 位输出请用 printf("%lld")