分析
本题考查并查集基本操作,首先将并查集初始化。
从前到后把每个字符串与在其之后的字符串进行比较,如果二者有两个对应位置上的字符不同的话就合并其所在的集合。
最后所有父亲是其自身的点的总数就是答案。
C++ 代码
class Solution {
public:
int n,m,ans;
vector<int> fa;
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
bool check(int a,int b,vector<string>& s) //判断两个字符串是否只有两个相对位置的不同
{
int co=0,idx1=-1,idx2=-1;
for(int i=0;i<m;i++)
{
if(s[a][i]!=s[b][i])
{
co++;
if(co==1) idx1=i;
else if(co==2) idx2=i;
else
return false; //有两个以上的位置不同,返回false
}
}
if(co==0) return true; //字符串完全相同,返回true
if(co==1) return false; //只有一个位置不同,返回false
if(s[a][idx1]==s[b][idx2] && s[a][idx2]==s[b][idx1]) //满足题意,返回true
return true;
return false;
}
int numSimilarGroups(vector<string>& strs) {
n=strs.size(),m=strs[0].size();
fa.resize(n);
for(int i=0;i<n;i++) fa[i]=i; //并查集初始化
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
int faa=find(i),fbb=find(j);
if(faa==fbb) continue;
if(check(i,j,strs))
{
fa[faa]=fbb;
}
}
}
for(int i=0;i<n;i++)
{
if(i==find(i)) //此时为1个大集合
ans++;
}
return ans;
}
};