题目的主要信息:
- 兄弟单词定义为:仅交换该单词字母顺序任意次,生成的单词
- 兄弟单词要求与原单词不同
- 现给定个单词,另外再给一个单词str,寻找上面个单词中str的兄弟单词里,按字典序排列后的第个单词
- 先输出兄弟单词个数,不足个兄弟单词则不输出单词
方法一:排序判断
具体做法:
我们用vector保存输入的全部单词,然后遍历这个vector,对每一个单词判断是否是str的兄弟单词,如果是加入我们的兄弟单词数组中。最后对兄弟单词数组进行排序,即可得到字典序的升序,然后输出这个vector数组的大小,超过的再输出第项。
判断两个单词是否是兄弟单词时,我们首先看长度是否一样,长度一样才有可能,然后看是否是相同的字符串,相同字符串则不是兄弟单词,最后我们对两个字符串分别以各自的字符排序,这样两个字符串都是一样的顺序,只要字符集和各个字符数量对得上,排序出来的单词应该是一样的,这就是兄弟单词。
#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;
}
复杂度分析:
- 时间复杂度:,其中为单词总数,为最大单词的长度,二者大小未知不可消除低次幂。判断函数外主要复杂度就是对brothers数组排序,这个数组最长就是单词总数,判断函数重要是对每个字符串内部排序,一共进行次
- 空间复杂度:,记录兄弟单词的字符串数组长度最大为
方法二:哈希表判断
具体做法:
判断函数外与方法一相同,但是判断部分我们可以借助无序哈希表,找到两个字符串的字符集和每个字符出现的次数,然后遍历第一个哈希表,如果能在第二个哈希表中找到相同的字符,且二者的value值都相同,则认为这个字符串出现的都一样,比较完整个哈希表都相同,则认为是兄弟单词。
#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;
}
复杂度分析:
- 时间复杂度:,中为单词总数,为最大单词的长度,二者大小未知不可消除低次幂。判断函数外主要复杂度就是对brothers数组排序,这个数组最长就是单词总数,判断函数都是无序哈希表操作,最大复杂度为,一共进行次
- 空间复杂度:,记录兄弟单词的字符串数组长度最大为,哈希表长度为单词字母集,不会超过52,属于常数