题目的主要信息:

  • 兄弟单词定义为:仅交换该单词字母顺序任意次,生成的单词
  • 兄弟单词要求与原单词不同
  • 现给定nn个单词,另外再给一个单词str,寻找上面nn个单词中str的兄弟单词里,按字典序排列后的第kk个单词
  • 先输出兄弟单词个数,不足kk个兄弟单词则不输出单词

方法一:排序判断

具体做法:

我们用vector保存输入的全部单词,然后遍历这个vector,对每一个单词判断是否是str的兄弟单词,如果是加入我们的兄弟单词数组中。最后对兄弟单词数组进行排序,即可得到字典序的升序,然后输出这个vector数组的大小,超过kk的再输出第kk项。

判断两个单词是否是兄弟单词时,我们首先看长度是否一样,长度一样才有可能,然后看是否是相同的字符串,相同字符串则不是兄弟单词,最后我们对两个字符串分别以各自的字符排序,这样两个字符串都是一样的顺序,只要字符集和各个字符数量对得上,排序出来的单词应该是一样的,这就是兄弟单词。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

bool isbrother(string s1, string s2){  //查看是否是兄弟单词
    if(s1.length() == s2.length()){ //兄弟单词一定要长度相等
        if(s1 == s2) //不能是同一个
            return false;
        sort(s1.begin(), s1.end());  //对两个字符串按字符字典序排序
        sort(s2.begin(), s2.end());
        if(s1 == s2) //排序后一样才是改变位置能办到的
            return true;
    }
    return false;
} 
int main(){
    int n;
    while(cin >> n){
        vector<string> strs(n);
        for(int i = 0; i < n; i++) //输入n个字符串
            cin >> strs[i];
        string str;
        cin >> str; //字符串str
        int k;
        cin >> k;
        vector<string> brothers;
        for(int i = 0; i < n; i++){ //检查每个字符串是否是兄弟单词
            if(isbrother(str, strs[i]))
                brothers.push_back(strs[i]);
        }
        sort(brothers.begin(), brothers.end()); //对后续排序
        cout << brothers.size() << endl;
        if(brothers.size() >= k) //输出第k个
            cout << brothers[k - 1] << endl;
    }
    return 0;
}

复杂度分析:

  • 时间复杂度:O(nlog2n+nmlog2m)O(nlog_2n+nmlog_2m),其中nn为单词总数,mm为最大单词的长度,二者大小未知不可消除低次幂。判断函数外主要复杂度就是对brothers数组排序,这个数组最长就是单词总数,判断函数重要是对每个字符串内部排序,一共进行nn
  • 空间复杂度:O(n)O(n),记录兄弟单词的字符串数组长度最大为nn

方法二:哈希表判断

具体做法:

判断函数外与方法一相同,但是判断部分我们可以借助无序哈希表,找到两个字符串的字符集和每个字符出现的次数,然后遍历第一个哈希表,如果能在第二个哈希表中找到相同的字符,且二者的value值都相同,则认为这个字符串出现的都一样,比较完整个哈希表都相同,则认为是兄弟单词。

alt

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

bool isbrother(string s1, string s2){
    if(s1.length() == s2.length()){ //兄弟单词一定要长度相等
        if(s1 == s2) //不能是同一个
            return false;
        unordered_map<char, int> mp1;
        unordered_map<char, int> mp2;
        for(int i = 0; i < s1.length(); i++) //将字符串1的所有字符加入哈希表1中统计出现次数
            mp1[s1[i]]++;
        for(int i = 0; i < s2.length(); i++) //将字符串2的所有字符加入哈希表2中统计出现次数
            mp2[s2[i]]++;
        auto it = mp1.begin();
        while(it != mp1.end()){ //遍历哈希表1
            if(mp2.find(it->first) == mp2.end() || mp2[it->first] != it->second){ //在哈希表2中找到表1遍历到的字符且查看value是否一样
                return false;
            }
            it++;
        }
        return true;
    }
    return false;
} 
int main(){
    int n;
    while(cin >> n){
        vector<string> strs(n);
        for(int i = 0; i < n; i++) //输入n个字符串
            cin >> strs[i];
        string str;
        cin >> str; //字符串str
        int k;
        cin >> k;
        vector<string> brothers;
        for(int i = 0; i < n; i++){ //检查每个字符串是否是兄弟单词
            if(isbrother(str, strs[i]))
                brothers.push_back(strs[i]);
        }
        sort(brothers.begin(), brothers.end()); //对后续排序
        cout << brothers.size() << endl;
        if(brothers.size() >= k) //输出第k个
            cout << brothers[k - 1] << endl;
    }
    return 0;
}

复杂度分析:

  • 时间复杂度:O(nlog2n+nm)O(nlog_2n+nm),中nn为单词总数,mm为最大单词的长度,二者大小未知不可消除低次幂。判断函数外主要复杂度就是对brothers数组排序,这个数组最长就是单词总数,判断函数都是无序哈希表操作,最大复杂度为O(m)O(m),一共进行nn
  • 空间复杂度:O(n)O(n),记录兄弟单词的字符串数组长度最大为nn,哈希表长度为单词字母集,不会超过52,属于常数