2306. 公司命名
已解答
困难
相关标签
相关企业
提示
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
- 从
ideas中选择 2 个 不同 名字，称为ideaA和ideaB。 - 交换
ideaA和ideaB的首字母。 - 如果得到的两个新名字 都 不在
ideas中，那么ideaA ideaB（串联ideaA和ideaB，中间用一个空格分隔）是一个有效的公司名字。 - 否则，不是一个有效的名字。
返回 不同 且有效的公司名字的数目。
思路：
首先，先思考两个什么样的名字才能满足条件组合，必须是首字母不同，且后缀不相同，才可能能组合。
因此，可以按照首字母划分，每个首字母保存对应的后缀。
对于两个名字，分别是prea，backa ，preb，backb，只有prea！=preb且backa！=backb才能组合，因此，只需要求出prea数组中，不包含backb的部分backa；和preb数组中，不包含backa的部分backb，相乘就是组合的个数。
而求prea中不是backb的部分，就是求backa和backb的差集，就是backa-（backa∩backb）。对另一边同理。而backa/backb可以直接得出来，因此只需要求两者的交集即可。求交集的时间最坏是O（nlogn），即各占n/2左右，每次找一个是否在另一个集合中是O（logn），因此最差是O（NlogN）。
class Solution {
public:set<string>hash[26];//前缀，和对应的所有后缀long long gets(set<string>&s1,set<string>&s2){ long long ans=0;for(auto &e:s1)if(s2.count(e))ans++;return ans;}long long distinctNames(vector<string>& ideas) {for(auto e:ideas){hash[e[0]-'a'].insert(e.substr(1,e.size()-1));}long long ans=0;for(int i=0;i<26;i++){for(int j=0;j<26;j++){if(i!=j){long long inter=gets(hash[i],hash[j]);ans+=(hash[i].size()-inter)*(hash[j].size()-inter);}}}return ans;// for(auto e:ideas)// newid.insert(e);// for(int i=1;i<ideas.size();i++)// for(int j=0;j<i;j++)// {// string s1=ideas[i],s2=ideas[j];// swap(s1[0],s2[0]);// // cout<<s1<<" "<<s2<<";";// if(newid.count(s1)==0&&newid.count(s2)==0)// ans.insert(s1+" "+s2),ans.insert(s2+" "+s1);// }// //暴力做法，死于两层循环时间到了n^2；// return ans.size();}
};
