题目的主要信息：

兄弟单词为只通过交换该单词字母顺序就可以变为待查找单词相同。同时，兄弟单词要求和原来的单词不同。
输入n个单词，从中找出所有的兄弟单词，输出兄弟单词的数量，以及输出指定的兄弟单词。

方法一：

遍历一遍所有单词，逐个判断当前单词words[i]是否为str的兄弟单词，若为兄弟单词则把它加到bros数组中，最后判断bros的大小，若为0，则表示没有兄弟单词，否则按照索引输出指定的兄弟单词。判断两个单词是否为兄弟单词，只需要对两个字符串的字符按照字母表排序，若排序后两个单词相同则为兄弟单词，前提是这两个单词不相同。同时需要注意的是，指定的兄弟单词索引是从1开始的，实际在bros中的索引应该为index-1。 alt

具体做法：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool isBrother(string str1, string str2){//判断是否为兄弟单词
    if(str1!=str2){//首先这两个单词不能相同
        sort(str1.begin(),str1.end());
        sort(str2.begin(),str2.end());
        //比较排序后的两个单词，若相同则为兄弟单词
        return str1==str2;
    }else return false;
}

int main(){
    vector<string> words;//保存所有单词
    vector<string> bros;//保存兄弟单词
    int n;//单词个数
    cin>>n;
    while(n){//逐个储存单词
        string word;
        cin>>word;
        words.push_back(word);
        n--;
    }
    string str;//带查找单词
    int index;//兄弟单词的索引
    cin>>str>>index;
    for(int i=0;i<words.size();i++){//遍历一遍所有单词，将兄弟单词储存出来
        if(isBrother(str,words[i])){
            bros.push_back(words[i]);
        }
    }
    if(bros.size()==0){//没有兄弟单词
        cout<<'0'<<endl;
    }else{
        sort(bros.begin(),bros.end());//对兄弟单词按照字典排序
        cout<<bros.size()<<endl;
        cout<<bros[index-1]<<endl;//索引从1开始，因此需要减1
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n + n m l o g_{2} m)$ ，对所有兄弟单词按字典排序时sort函数的时间复杂度为 $O (n l o g_{2} n)$ ,每一个is_Brother的时间复杂度是 $O (m l o n g_{2} m)$ ,总共要做n次is_Brother的判断。
空间复杂度： $O (n)$ ，最坏情况下，所有单词都是兄弟单词。

方法二：

在判断是否为兄弟单词的时候还可以用计数法，即统计每个26个字母在单词中出现的频数，若两个单词的在26个字母上的频数分布完全相同，切这两个单词本身不相同，那么这两个单词就是兄弟单词。我们用count数组来记录单词在26个字母上的频数分布，用str[i]-'a'来记录相对位置。

具体做法：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool isBrother(string str1, string str2){//判断是否为兄弟单词
    if(str1==str2) return false;//两单词相同不是兄弟单词
    int count1[26]={0};
    int count2[26]={0};
    for(int i=0;i<str1.size();i++){//统计str1中各字母出现的次数
        count1[str1[i]-'a']++;
    }
    for(int i=0;i<str2.size();i++){//统计str2中各字母出现的次数
        count2[str2[i]-'a']++;
    }
    for(int i=0;i<26;i++){//判断str1和str2中字母种类和个数是否完全相同
        if(count1[i]!=count2[i]) return false;
    }
    return true;
}

int main(){
    vector<string> words;//保存所有单词
    vector<string> bros;//保存兄弟单词
    int n;//单词个数
    cin>>n;
    while(n){//逐个储存单词
        string word;
        cin>>word;
        words.push_back(word);
        n--;
    }
    string str;//带查找单词
    int index;//兄弟单词的索引
    cin>>str>>index;
    for(int i=0;i<words.size();i++){//遍历一遍所有单词，将兄弟单词储存出来
        if(isBrother(str,words[i])){
            bros.push_back(words[i]);
        }
    }
    if(bros.size()==0){//没有兄弟单词
        cout<<'0'<<endl;
    }else{
        sort(bros.begin(),bros.end());//对兄弟单词按照字典排序
        cout<<bros.size()<<endl;
        cout<<bros[index-1]<<endl;//索引从1开始，因此需要减1
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n l o g_{2} n + n m)$ ，sort函数的时间复杂度为 $O (n l o g_{2} n)$ ，isBrother函数需要遍历一遍当前字符串，时间复杂度为 $O (m)$ ，总共需要遍历n'次。
空间复杂度： $O (n)$ ，最坏情况下，所有单词都是兄弟单词。

题解 | #查找兄弟单词#

题目的主要信息：

方法一：

方法二：