leetcode 2157. 字符串分组

 1 const int N=2e4+5;
 2 int fa[N],sz[N],G[N];
 3 class Solution {
 4 public:
 5     
 6     inline int fd(int x){return fa[x]==x?x:fa[x]=fd(fa[x]);}
 7     inline void merge(int x,int y)
 8     {
 9         int a=fd(x),b=fd(y);
10         if(a==b)return;
11         sz[a]+=sz[b];
12         fa[b]=a;
13     }
14     vector<int> groupStrings(vector<string>& words) {
15         int n=words.size();
16         for(int i=0;i1;fa[i]=i;}
17         unordered_map<int,int>mp;
18         for(int i=0;i)
19         {
20             int mask=0;
21             for(auto &p:words[i])mask|=(1<<(p-'a'));
22             if(mp.count(mask)) merge(i,mp[mask]);
23             mp[G[i]=mask]=i;
24         }
25         for(int i=0;i)
26         {
27             int mask=G[i];
28             for(int j=0;j<26;j++)
29             {
30                 int nx=mask^(1<<j);
31                 if(mp.count(nx)) merge(i,mp[nx]);
32             }
33         
34             for(int j=0;j<26;j++)
35             if(mask>>j&1)
36             for(int k=0;k<26;k++)
37             if(k!=j&&(!(mask>>k&1)))
38             {
39                 int nx=mask^(1<1<<k);
40                 if(mp.count(nx))merge(i,mp[nx]);//这里卡常太严重了；
41             }
42         }
43         int mx=0,cnt=0;
44         for(int i=0;i)
45         {
46             if(fd(i)==i)cnt++;
47             mx=max(mx,sz[i]);
48         }
49        return {cnt,mx};
50     }
51 };